Sample Input

3 4
1 2 3 4
1 2 3 4
1 2 3 5

Sample Output

7

Sample Input

8 3 2
3 11
8 7
6 3

Sample Output

6 6 5 5 5 4 3 3

Sample Input 1

2 2
-1 1

Sample Output 1

2

Sample Input 2

2 3
-1 0

Sample Output 2

12

Giải thích

Ở ví dụ 1:
Cách 1: Giây 1 𝑇(1), giây 2 𝑃(2)
Cách 2: Giây 1 𝑃(2), giây 2 𝑇(1)

Ở ví dụ 2:
Cách 1: Giây 1 𝑇(1), giây 2 𝑁𝑜𝑛𝑒, giây 3 𝑁𝑜𝑛𝑒
Cách 2: Giây 1 𝑇(1), giây 2 𝑇(2), giây 3 𝑃(2)
Cách 3: Giây 1 𝑇(1), giây 2 𝑃(2), giây 3 𝑇(2)
Cách 4: Giây 1 𝑇(1), giây 2 𝑃(1), giây 3 𝑇(1)
Cách 5: Giây 1 𝑇(1), giây 2 𝑇(1), giây 3 𝑃(1)
Cách 6: Giây 1 𝑃(1), giây 2 𝑇(1), giây 3 𝑇(1)
Cách 7: Giây 1 𝑁𝑜𝑛𝑒, giây 2 𝑇(1), giây 3 𝑁𝑜𝑛𝑒
Cách 8: Giây 1 𝑁𝑜𝑛𝑒, giây 2 𝑁𝑜𝑛𝑒, giây 3 𝑇(1)
Cách 9: Giây 1 𝑇(2), giây 2 𝑇(1), giây 3 𝑃(2)
Cách 10: Giây 1 𝑇(2), giây 2 𝑃(2), giây 3 𝑇(1)
Cách 11: Giây 1 𝑃(2), giây 2 𝑇(2), giây 3 𝑇(1)
Cách 12: Giây 1 𝑃(2), giây 2 𝑇(1), giây 3 𝑇(2)
Trong đó:
𝑇(𝑖) - nháy chuột trái vào xạ thủ thứ 𝑖;
𝑃(𝑖) - nháy chuột phải vào xạ thủ thứ 𝑖;
𝑁𝑜𝑛𝑒 - không làm gì cả.

Sample Input 1

6
abacac

Sample Output 1

6

Sample Input 2

1
e

Sample Output 2

0

Sample Input 3

5
aaaaa

Sample Output 3

6

Sample Input 1

5 6
1 2 2
2 3 1
2 4 3
3 4 5
3 5 2
4 5 4
3
4 5 2

Sample Output 1

8

Sample Input 2

4 3
1 2 1
2 3 1
3 4 1
2
1 3

Sample Output 2

2

Sample Input

10 4
4 1 12 17 7 3 6 8 10 16

Sample Output

94

Giải thích