Codah ClubTrain. Submit. Improve.
Sign in
English
#000184

z-keyboard

Little Z has made a device that can detect what a person is typing on a keyboard based on the sound that the keyboard makes. However, the device sometimes makes mistakes.

One day, Little Z by accident deleted the file that described which key corresponds to which sound, and now he wants to reconstruct that.

In order to do that, he assigned random keys to the possible sounds, and now, if he types "aaabbb", the detector might detect "wwwtty", we see that the last letter was actually a detection error.

His plan is to type a long text, that contains only 26 letters of the English alphabet, and then look at the output of the device, in order to modify the key assignments.

Your job is to help Little Z assign the letters so that the total number of detection errors on the typed text is minimized.

Since the typed text is too long, Little Z modified the device to report only how many times each key was pressed.



InputFrom the first line of the standard input read an integer n (1 <= n <= 1000000). n represents the length of the typed text. From the second line read n characters representing the typed text. After that, from the third line read 26 integers, representing the numbers of times each different key was detected. The sum of the numbers in the third line will equal to n.


OutputTo the standard output write one integer, representing the minimal total number of errors that Little Z can achieve with some assignment of keys


Input:
6
aaabbb
3 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Output:
1
Explanation: We can assign the first key to 'a' and the third key to 'b'. It doesn't matter how we assign the rest of the keys, we will always get 1 error

Input:
26
qwertyuiopasdfghjklzxcvbnm
25 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Output:
24

Input:
26
qwertyuiopasdfghjklzxcvbnm
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0
Output:
1

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.