495. Make the Rope Colorful

0

Medium

Alice has a rope with n balloons arranged on it. She wants the rope to be colorful and not have consecutive balloons of the same color. Alice asks for your help to make the rope colorful in the shortest possible time. You are given a string colors, where colors[i] represents the color of the ith balloon. You can remove some balloons from the rope to achieve the desired result. The time needed to remove each balloon is given in the integer array neededTime. Return the minimum time required to make the rope colorful.

Input Format

The first line of the input contains an integer n, representing the number of balloons. The next line contains a string color, which represents the color of each balloon. The following n lines contain an integer array needTime, which represents the time required to remove each balloon.

Output Format

Return an integer representing the minimum time required to make the rope colorful.

Example

Input

5 abaac 1 2 3 4 5

Output

3

Constraints

  • n == colors.length == neededTime.length
  • 1 <= n <= 10^5
  • 1 <= neededTime[i] <= 10^4
  • colors contains only lowercase English letters.
    • Loading...

    View Submissions

    Console