rt

Samples2.in

8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8

Samples2.in

27
18
19
19

Samples3.in

12 15
15 9 3 15 9 3 3 8 16 9 3 17
2 7
2 5
2 2
1 12
4 12
3 6
11 12
1 7
2 6
3 5
3 10
7 10
1 4
4 8
4 8

Samples3.in

18
18
9
30
18
15
17
30
18
15
18
16
30
15
15