Độ khó: Trung bình (2/4 điểm)

Sample Input 1

7 2
4 10
4 10
4 10
3 20
2 1
2 1
1 10

Sample Output 1

3

Sample Input 2

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

Sample Output 2

4

Độ khó: Khá (3/4 điểm)

Sample Input

4
10 2
99 5
123456789 9
999999999 100

Sample Output

3
8
482256
21

Độ khó: Trung bình (2/4 điểm)

Sample Input

3
4 5
1 2 1 4
1 2 4 9 10
2 2
1 1
0 1
3 1
1000000000 1000000000 1000000000
1000000000

Sample Output

1 4 8 8 8 
0 2 
3000000000

Độ khó: Trung bình (2/4 điểm)

Sample Input

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

Sample Output

2

Độ khó: Khá (3/4 điểm)

Sample Input

6
10 20
20 10
1 5
50 100
100 1
2 200

Sample Output

4