888. Make the Rope Colorful

0

Medium

Alice has n balloons arranged on a rope.

Alice wants the rope to be colorful. And also she does not want the color of rope is monotonous anytime which means she does not want two consecutive balloons to be of the same color.

As you are the best friend of Alice so she ask you to make the rope in minimum time.

You are given a 0-indexed string colors where colors[i] is the color of the ith balloon.

You can remove some balloons from the rope to make it colorful.

You are given a 0-indexed integer array neededTime where neededTime[i] is the time (in seconds) that you needs to remove the ith balloon from the rope. Return the minimum time you needs to make the rope colorful.

Alice wants the rope to be colorful. And also she does not want the color of rope is monotonous anytime which means she does not want two consecutive balloons to be of the same color.

As you are the best friend of Alice so she ask you to make the rope in minimum time.

You are given a 0-indexed string colors where colors[i] is the color of the ith balloon.

You can remove some balloons from the rope to make it colorful.

You are given a 0-indexed integer array neededTime where neededTime[i] is the time (in seconds) that you needs to remove the ith balloon from the rope. Return the minimum time you needs to make the rope colorful.

Input Format

First line of input contains an integer n representing the number of balloons.

Next line contains a string color which represent the color of ith balloon

Follong n line contains an integer array needTime which represent the required time to remove ith balloon.

Next line contains a string color which represent the color of ith balloon

Follong n line contains an integer array needTime which represent the required time to remove ith balloon.

Output Format

Return an integer the minimum time you needs to make the rope colorful.

Example

Input

5
abaac
1 2 3 4 5

Output

3

Constraints

Loading...

View Submissions

Console