VD1

Input

9 21

Output

2

Nguồn

VD1

Input

abaabaabaabaabaaba

Output

2

VD2

Input

xbya

Output

1

Nguồn

Ví dụ:

Input

4 1
1 4 5 10 3 2 8 6

Output

2

Nguồn

Ví dụ 1:

Input

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

Output

16
16
20

Ví dụ 2:

Input

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

Output

5
11
15

Nguồn