DWITE Contest

Test Case for Question #4 in DWITE 2008-2009 High School Round 2

Contest: DWITE 2008-2009 High School Round 2
Question: #4
Input File: DATA4.txt
Output File: OUT4.txt


Input

100
3
100 999
50 500
50 500

100
4
50 100
25 100
25 100
1 101

100
5
20 100
40 100
40 100
20 60
20 60

100
4
49 100
51 1000
50 600
50 600

77
20
2 2
3 3
5 5
7 7
11 11
13 13
17 17
19 19
23 23
29 29
31 31
37 37
41 41
43 43
47 47
53 53
59 59
61 61
67 67
71 71




Output

1000
301
320
1200
77