===INPUT===
10 25
4 5 22 1 4
3 9 20 17
5 18 8 16 15 5
3 7 2 12
12 19 15 23 5 21 24 13 16 11 9 20 4
9 12 4 19 16 6 18 5 2 23
7 22 15 6 8 5 17 24
5 25 1 3 21 14
5 9 18 6 11 2
9 5 7 17 24 22 10 12 4 25
30
19 11
24 17
9 1
19 13
25 13
11 5
7 17
20 24
10 16
24 10
2 18
20 11
3 4
12 3
21 3
7 2
24 8
16 1
19 11
14 17
11 22
5 23
21 18
12 5
4 10
3 25
15 8
1 12
4 22
1 6
===OUTPUT===
3
===END===