Nhân dịp sinh nhật, Tahp mua tặng bé Trung một bộ đồ chơi sắp xếp xâu và đố Trung giải được, nếu thành công sẽ dẫn Trung đi uống tà tưa. Bộ đồ chơi có một xâu ~s~ gồm ~n~ chữ cái tiếng Anh in thường. Mục tiêu của trò chơi là tìm cách sắp xếp các kí tự của xâu ~s~ sao cho cuối cùng thu được xâu ~t~.

Không được thông minh cho lắm, vì vậy Trung quyết định chơi ăn gian. Tại mỗi lượt, cậu sẽ chọn một đoạn các kí tự từ ~l~ đến ~r~ trên xâu ~s~, sau đó tháo các kí tự trong đoạn này ra và lắp lại theo ý thích của mình. Với mỗi vị trí ~i~ trên xâu ~s~, để tháo và lắp kí tự ở vị trí này tốn lượng thời gian ~a_i~ giây. Giá trị ~a_i~ chỉ tương ứng với vị trí ~i~, và không thay đổi sau khi ta đã xáo trộn các kí tự.

Ngoài ra, Trung không muốn tháo ra lắp vào bộ đồ chơi quá ~k~ lượt vì sợ làm hỏng nó. Hãy tính thời gian nhỏ nhất Trung cần bỏ ra để hoàn thành trò chơi này.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~k~ (~1 \le n \le 10^5~, ~1 \le k \le 10^5~) — lần lượt là độ dài của hai xâu kí tự, và số lần lắp ráp tối đa mà Trung có thể thực hiện.

Dòng thứ hai gồm một xâu ~s~ độ dài ~n~ chứa các chữ cái tiếng Anh in thường — xâu ban đầu trong bộ đồ chơi.

Dòng thứ ba gồm một xâu ~t~ độ dài ~n~ chứa các chữ cái tiếng Anh in thường — xâu mục tiêu mà bé Trung muốn đạt được.

Dòng cuối cùng gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq 10^9~) — thời gian cần thiết để tháo ra và lắp vào của các vị trí trên xâu ~s~.

Dữ liệu đảm bảo luôn tồn tại cách để đưa xâu ~s~ về giống xâu ~t~.

Output

Một số nguyên duy nhất là thời gian tối thiểu Trung cần bỏ ra.

Scoring

• Subtask 1 (~750~ điểm): ~n, k \leq 100~.

• Subtask 2 (~500~ điểm): ~n \leq 10^5, k \leq 100~.

• Subtask 3 (~750~ điểm): không có ràng buộc gì thêm.

Tổng số điểm nhận được nếu bạn giải thành công bài toán này là ~2000~ điểm.

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

Trong ví dụ đầu tiên:

• Lần thứ nhất, Trung chọn đoạn ~[1, 2]~ và tạo ra xâu bacabcbab, tốn ~3~ giây.

• Lần thứ hai, Trung chọn đoạn ~[5, 9]~ và tạo ra xâu bacacbbba, tốn ~15~ giây.

Trong ví dụ thứ hai:

• Trung chọn đoạn ~[2, 7]~ và tạo ra xâu toanphat, tốn ~27~ giây.