On the occasion of his birthday, Tahp bought Trung a string-sorting toy set and challenged Trung to solve it. If successful, Tahp will take Trung out for a treat. The toy set has a string ~s~ consisting of ~n~ lowercase English letters. The goal of the game is to rearrange the characters of string ~s~ to obtain the string ~t~.

Not being very smart, Trung decides to cheat. At each turn, he will choose a segment of characters from ~l~ to ~r~ on string ~s~, remove the characters in this segment and then rearrange them as he wishes. For each position ~i~ on string ~s~, it takes ~a_i~ seconds to remove and rearrange the character at that position. The value of ~a_i~ corresponds only to position ~i~, and does not change after shuffling the characters.

In addition, Trung does want to remove and rearrange the toy set no more than ~k~ times because he fears that he might damage it. Calculate the minimum time Trung needs to complete this game.

Input

The first line contains two positive integers ~n~ and ~k~ (~1 \le n \le 10^5~, ~1 \le k \le 10^5~) — the length of the two character strings, and the maximum number of times Trung can assemble and disassemble the toy set.

The second line contains a string ~s~ of length ~n~ consisting of lowercase English letters — the initial string in the toy set.

The third line contains a string ~t~ of length ~n~ consisting of lowercase English letters — the target string that Trung wants to achieve.

The last line contains ~n~ positive integers ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq 10^9~) — the time required to remove and rearrange the characters at each position on string ~s~.

The data always ensures that there is a way to make string ~s~ identical to string ~t~.

Output

A single integer is the minimum time Trung needs to spend.

Scoring

• Subtask 1 (~750~ points): ~n, k \leq 100~.

• Subtask 2 (~500~ points): ~n \leq 10^5, k \leq 100~.

• Subtask 3 (~750~ points): no additional constraints.

If you solve this problem, you will receive ~2000~ points.

Sample Input 1

9 2
abcabcbab
bacacbbba
1 2 4 6 2 1 7 3 2

Sample Output 1

18

Sample Input 2

8 1
tahpnaot
toanphat
5 7 3 2 8 5 2 4

Sample Output 2

27

Notes

In the first example:

• The first time, Trung chooses the segment ~[1, 2]~ and creates the string bacabcbab which takes ~3~ seconds.

• The second time, Trung chooses the segment ~[5, 9]~ and creates the string bacacbbba which takes ~15~ seconds.

In the second example:

• Trung chooses the segment ~[2, 7]~ and creates the string toanphat which takes ~27~ seconds.