Ví dụ:

Input

4 0
abaa
bcba

Output

6

Ví dụ 2:

Input

6 2
cbccac
bacbca

Output

20

Nguồn

Ví dụ:

Input

10 8 3
1 3 9
1 9 2
2 3 5
3 7 8
4 6 5
5 7 1
6 7 1
7 8 1
9 10 1

Output

34

Nguồn

Ví dụ:

Input

5 4
20 10 12 18 15
3 4
4 1
1 3
4 2

Output

11 10 10 9 8

Nguồn