solution of http://www.acm-japan.org/past-icpc/domestic2003/B.htm

B1.txt

16
10 8
10 5
8 1
5 3
2 1
1 5
3 8
9 2
3 1
8 5
6 6
3 3
7 3
9 1
4 7
6 8
8 3
4 3
499
99 90
23 24
93 65
20 83
97 54
60 75
78 7
31 20
65 40
30 55
9 55
59 70
85 64
94 43
44 45
54 58
32 11
54 61
55 45
87 43
78 9
64 47
7 20
56 87
48 31
31 84
20 8
34 5
7 82
38 84
34 44
96 38
61 3
87 52
18 74
68 69
18 84
52 22
20 15
90 85
90 30
22 53
9 64
13 33
82 66
62 14
36 38
78 87
2 20
13 11
38 15
14 62
6 27
74 34
69 10
89 48
82 30
65 90
66 30
3 20
21 19
60 38
51 72
2 7
35 82
39 84
89 80
11 7
66 23
25 64
35 17
64 43
95 58
70 62
75 90
60 71
45 60
71 86
95 53
56 84
6 74
75 21
34 20
54 9
61 43
52 75
84 51
88 50
45 22
75 18
48 63
52 20
12 76
85 86
90 68
32 5
31 79
88 37
89 52
61 12
20 3
41 38
26 74
78 32
86 70
85 78
85 8
23 87
54 36
1 44
49 84
40 78
36 73
42 79
68 31
71 51
13 48
88 47
39 85
6 50
17 36
55 29
23 6
97 50
86 68
21 15
25 51
11 4
86 78
80 81
52 6
42 64
63 1
2 47
92 59
22 72
92 5
10 60
53 86
89 64
99 74
69 85
68 42
79 81
27 42
7 60
11 75
40 62
73 14
70 46
43 38
72 89
67 89
49 65
84 39
56 19
47 77
2 69
98 25
67 70
37 55
3 36
19 33
17 37
80 39
55 41
74 71
6 21
60 24
39 14
67 4
37 69
97 80
48 55
60 30
37 60
27 19
1 34
45 24
26 61
99 72
23 27
41 71
56 89
14 67
13 60
77 65
47 66
79 2
37 37
74 63
97 20
25 23
42 60
73 49
67 72
67 33
25 53
14 17
6 70
73 25
3 77
60 39
23 67
40 58
76 85
30 71
14 72
66 28
24 11
21 34
8 69
92 41
11 5
9 38
12 73
31 80
57 52
9 22
10 31
7 48
54 81
92 28
73 32
54 19
99 43
78 55
91 79
57 11
65 1
82 74
73 85
44 3
62 43
22 26
35 2
8 60
46 26
6 62
10 48
8 8
18 38
80 18
53 80
8 71
98 89
88 24
1 41
98 53
82 64
32 42
47 37
2 18
33 59
8 43
61 31
50 68
96 73
85 56
62 37
61 14
80 14
28 42
79 25
39 61
43 59
74 24
5 75
77 29
80 82
78 21
93 44
16 15
53 45
34 49
71 77
41 9
47 20
22 85
79 82
53 17
49 19
26 17
90 58
7 41
43 45
93 38
86 71
55 90
57 72
11 1
14 85
25 49
67 17
41 19
6 57
96 36
46 11
78 46
24 75
3 19
83 4
20 87
38 48
84 13
18 77
21 11
42 88
86 9
87 25
52 74
18 75
47 80
66 34
96 26
7 44
51 8
90 61
56 83
43 13
21 23
33 32
87 84
84 54
83 6
96 43
81 60
72 36
28 68
34 34
64 28
21 82
53 58
81 30
17 2
52 31
41 47
22 77
8 40
91 49
37 32
14 70
56 22
61 18
51 38
16 34
75 54
68 26
11 74
19 54
46 17
7 84
7 86
96 23
15 24
46 47
46 18
12 70
80 43
99 48
74 45
28 24
97 47
86 34
64 5
84 17
2 42
19 89
54 55
43 82
61 88
5 68
13 40
33 77
75 51
26 25
97 30
44 70
93 85
59 56
80 60
41 24
74 86
58 78
93 73
67 61
58 25
99 90
64 18
50 87
43 56
99 63
6 23
94 78
98 71
16 40
12 12
73 22
50 13
98 59
50 47
36 8
42 53
97 6
6 56
93 37
91 81
72 15
29 12
92 81
18 7
1 47
61 55
12 38
5 1
49 25
72 48
57 42
18 90
18 5
98 63
68 51
98 49
83 27
4 28
51 66
77 61
47 65
23 14
48 16
66 31
74 75
79 85
53 51
82 34
19 24
79 57
65 21
22 48
1 88
20 40
44 33
98 9
35 49
49 71
44 50
75 28
52 52
49 21
48 30
70 28
8 74
48 37
21 22
19 66
91 83
69 6
33 39
24 47
85 88
45 74
83 90
47 42
33 24
24 2
78 76
48 6
2 41
86 8
56 45
13 61
20 79
53 41
5 6
31 33
14 49
19 18
70 60
95 28
52 2
95 49
64 48
42 40
64 61
3 29
84 38
9 62
22 4
31 77
97 34
26 86
24 77
84 40
90 41
9 75
26 19
68 38
22 86
62 13
4 53
6 8
200
80 50
2 33
65 33
48 21
79 8
4 26
55 6
44 32
39 50
32 42
50 50
8 28
20 29
45 49
56 44
43 12
27 26
56 3
8 46
23 39
43 39
64 17
66 39
71 34
18 2
68 37
33 45
36 13
24 22
73 49
78 16
30 14
31 8
18 1
13 42
61 7
50 6
55 28
54 25
11 32
18 38
10 31
73 36
29 7
14 26
34 16
1 15
33 8
55 25
10 7
3 31
62 7
78 5
22 19
26 9
6 8
41 40
33 37
45 1
14 1
7 17
6 17
63 40
57 49
66 26
55 48
28 16
44 16
71 37
66 8
8 43
35 40
53 9
47 29
32 20
59 40
58 46
28 21
5 34
29 50
21 26
9 19
71 5
26 13
21 21
61 40
60 47
66 6
6 9
37 4
38 14
80 5
6 36
69 7
58 49
22 36
9 24
70 4
57 33
76 9
22 41
35 1
17 42
26 14
20 32
38 47
28 19
42 35
56 42
51 43
22 24
19 11
68 20
16 34
2 42
32 26
72 38
56 20
70 34
14 29
47 3
66 16
23 29
11 28
72 41
63 13
5 1
43 14
67 26
22 40
4 8
41 17
17 28
51 14
33 43
44 45
23 15
56 45
47 2
37 2
35 18
52 13
53 25
22 43
69 30
61 22
48 33
41 26
12 11
1 5
36 34
71 28
78 36
62 26
9 18
69 3
77 20
47 30
64 18
54 34
60 46
76 39
39 48
74 40
30 6
46 15
69 47
42 38
34 15
13 23
72 42
37 19
73 44
70 9
23 23
12 12
61 49
12 1
58 15
20 8
30 38
72 10
6 16
67 19
40 12
33 12
65 20
52 17
25 31
17 27
35 21
1 25
19 42
65 17
49 17
36 30
6 47
80 41
44 38
1 44
49 4
3 10
499
90 99
67 13
25 64
74 93
68 57
45 51
30 29
31 98
17 59
29 45
3 9
54 1
72 92
80 26
73 65
39 16
44 51
38 14
4 3
16 69
50 96
56 96
87 95
22 4
35 57
19 37
65 79
27 71
9 16
33 99
26 60
33 4
9 43
8 21
90 21
44 3
7 8
53 39
19 90
67 53
47 85
52 10
28 24
80 36
55 75
78 16
17 48
73 44
52 34
89 32
27 52
25 69
14 30
87 59
36 45
85 62
19 98
26 90
85 49
44 56
51 57
53 57
14 88
17 90
40 60
40 73
57 53
23 68
26 46
26 97
44 36
14 15
79 28
32 55
45 98
31 80
71 87
57 51
32 87
64 99
85 19
59 98
24 31
88 11
55 30
82 85
26 79
31 49
14 87
5 40
12 62
27 35
40 83
3 24
50 93
14 27
19 71
23 96
29 65
52 27
74 50
75 37
74 23
67 58
89 60
17 89
67 14
68 68
88 7
10 63
7 13
53 7
20 11
29 82
19 6
54 66
47 19
12 82
30 85
41 44
72 37
52 64
23 54
77 45
60 21
81 57
85 95
52 14
42 62
23 79
32 3
63 24
1 45
31 57
75 44
19 72
27 31
22 65
3 43
22 81
70 17
50 59
82 82
21 22
23 86
67 2
53 40
82 12
6 73
64 94
45 36
18 80
46 10
7 39
44 27
55 50
59 95
54 68
66 28
78 35
50 9
45 22
30 80
6 42
26 85
73 98
3 61
13 84
14 20
58 21
62 40
42 84
87 75
79 8
55 38
60 15
82 76
79 94
65 64
70 9
76 70
32 70
88 97
78 71
7 40
90 82
78 41
67 73
58 58
56 88
7 57
55 2
31 18
2 82
43 15
24 29
28 79
80 32
38 2
56 90
77 10
54 62
13 28
54 97
20 52
80 46
90 47
27 17
82 87
40 76
53 11
26 22
16 28
85 42
70 62
87 85
59 99
77 58
40 95
54 78
65 98
58 98
25 84
79 70
63 46
44 86
19 97
42 95
5 27
28 38
69 87
30 10
85 32
20 77
90 64
55 72
26 76
52 6
68 85
28 31
30 18
78 84
13 20
43 35
27 14
52 32
3 83
59 2
7 47
56 14
46 26
7 89
56 47
47 99
75 2
78 87
85 27
52 62
16 49
6 74
20 17
19 40
81 14
59 81
10 6
14 14
74 31
51 64
75 33
30 45
20 51
62 24
75 31
73 84
68 51
74 76
48 12
88 81
41 1
60 50
85 64
27 95
13 21
21 23
87 23
22 70
36 36
11 81
46 63
47 24
84 22
34 77
85 12
3 51
12 17
47 13
7 62
87 71
36 62
30 32
29 58
10 55
58 90
45 58
26 98
88 64
83 77
22 48
77 94
36 95
9 98
17 87
40 11
86 39
81 50
69 55
90 67
44 1
21 43
31 8
51 36
78 59
74 9
6 96
46 3
19 10
8 96
69 56
61 53
84 76
13 60
32 10
63 37
82 81
87 65
64 55
13 11
62 79
68 62
34 95
71 77
44 66
88 95
37 25
27 20
66 2
36 9
56 36
6 14
63 73
22 97
71 8
7 87
66 11
59 64
32 19
12 72
89 4
51 59
21 78
58 48
77 93
45 73
89 80
62 38
15 70
54 82
84 28
56 5
1 94
15 32
34 6
21 75
36 96
32 28
21 89
75 59
73 54
13 89
8 74
1 11
78 70
56 99
7 82
47 88
32 23
19 65
11 19
20 35
33 69
78 89
49 35
74 38
53 77
64 22
31 53
57 91
41 20
52 19
56 89
68 78
83 21
23 37
48 76
62 54
54 32
5 1
73 87
35 64
70 12
17 99
46 37
19 88
28 19
66 60
85 85
53 36
74 20
73 91
53 55
57 10
62 82
59 91
50 57
19 2
30 69
27 66
16 16
81 61
43 28
10 29
38 99
17 31
35 71
29 87
87 38
15 77
47 89
48 49
38 22
87 13
25 48
14 94
81 29
83 97
74 74
33 67
26 83
43 87
61 15
18 76
79 67
26 71
29 19
55 1
11 69
57 27
35 88
75 77
35 74
72 71
83 95
2 18
76 33
40 29
38 73
14 98
13 55
22 94
73 83
31 10
88 6
81 66
28 54
71 7
18 14
5 73
80 15
79 83
63 91
9 14
49 1
86 50
76 40
70 87
76 83
27 82
23 82
16 91
79 60
30 65
4 10
50 20
84 20
72 3
45 71
62 91
63 82
86 64
49 74
15 10
120
40 60
28 26
14 37
5 18
23 53
24 3
15 3
17 29
12 28
13 37
11 24
12 47
6 35
31 30
4 36
39 4
33 19
22 6
15 6
35 9
38 18
11 45
40 27
25 3
34 17
39 56
32 43
2 29
37 52
18 32
19 37
36 51
27 49
16 41
34 2
21 44
19 51
28 31
17 24
5 2
32 56
37 3
38 38
4 46
21 21
18 39
29 45
10 35
13 17
7 18
11 47
21 29
17 20
31 45
35 16
26 6
31 34
1 40
3 24
5 15
24 42
14 33
18 15
19 50
23 6
20 33
12 60
14 29
32 44
5 46
31 43
12 53
36 44
32 11
7 57
5 42
10 10
26 48
24 5
9 39
30 28
20 48
21 31
24 18
28 14
40 51
27 15
34 30
25 32
6 50
6 56
39 11
35 15
27 55
5 8
23 47
1 34
15 13
36 58
30 3
3 21
6 1
16 11
31 52
23 48
13 40
3 32
2 9
18 49
24 22
28 18
40 40
31 26
25 46
35 6
40 10
27 25
10 2
28 40
25 2
21 2
10 8
499
99 90
71 22
57 18
77 88
88 72
57 52
90 27
7 35
31 84
23 13
3 7
42 35
18 57
39 74
49 3
85 90
18 63
66 81
78 15
78 64
41 62
53 76
95 57
82 53
50 23
56 15
54 86
4 42
14 76
61 33
61 18
23 67
98 15
48 32
29 6
39 76
56 82
97 78
48 5
76 60
79 66
45 69
24 46
2 37
85 7
97 71
6 63
18 65
5 27
76 67
86 25
97 60
5 75
90 78
70 10
45 68
92 6
80 61
33 80
50 43
41 38
60 71
63 84
45 11
39 65
96 52
33 1
65 28
84 44
85 26
18 75
3 1
17 62
25 2
60 29
63 46
20 30
44 53
95 33
45 5
5 50
55 19
31 2
71 87
70 75
67 60
84 76
96 63
48 82
44 8
91 70
7 63
25 41
88 46
35 49
50 3
70 68
73 73
22 81
15 38
99 53
77 9
47 29
80 47
90 59
1 16
29 32
85 61
52 26
70 69
3 27
24 45
23 16
72 35
40 57
34 84
62 3
18 19
83 87
99 26
19 81
51 54
2 81
96 18
8 1
41 53
82 80
77 32
59 85
46 24
31 24
35 84
89 33
1 18
47 90
43 83
97 46
8 26
26 32
52 67
66 90
38 21
53 87
50 46
61 4
7 17
72 48
80 52
89 35
31 70
78 35
98 1
61 70
69 41
9 31
15 56
10 7
21 33
64 52
70 59
64 20
10 81
13 9
94 19
68 86
34 53
94 22
17 73
35 41
39 77
6 53
15 24
3 80
73 37
4 59
84 20
15 3
2 16
81 66
23 68
17 84
93 54
85 83
63 29
94 72
58 27
52 18
12 16
6 82
16 25
23 18
71 89
90 16
60 45
64 10
22 15
37 13
86 83
21 65
37 51
46 49
12 41
65 13
47 50
4 69
74 54
57 27
61 29
14 28
17 86
99 56
53 16
49 39
54 87
83 81
82 20
85 10
22 30
13 39
16 26
26 62
43 26
32 2
25 54
21 51
20 81
79 72
51 8
9 66
93 46
93 66
18 58
66 10
24 7
3 75
93 26
26 34
6 57
35 67
1 26
72 83
68 4
90 74
73 8
88 67
41 4
86 41
41 44
81 61
44 2
67 87
6 9
25 84
1 88
91 25
44 49
18 68
77 54
31 42
56 53
8 87
20 66
98 31
2 8
99 9
52 12
13 20
36 73
94 71
59 83
5 73
41 85
33 34
10 88
11 2
77 18
59 67
11 49
51 64
36 23
53 40
14 2
41 67
99 71
81 67
17 14
58 66
6 61
73 32
49 47
78 69
98 83
19 70
93 15
17 72
17 40
10 84
30 4
76 38
81 31
84 61
42 76
55 27
29 8
58 14
9 1
99 79
72 90
11 9
84 63
89 64
91 24
28 66
45 40
49 63
59 40
24 37
71 31
44 34
2 83
72 53
36 53
12 51
86 23
68 79
47 10
68 21
52 32
59 60
97 61
23 65
37 27
57 87
21 37
1 57
99 1
28 36
44 22
60 55
98 52
62 31
45 59
60 68
9 57
9 74
14 9
73 43
49 29
68 49
13 31
22 13
1 64
77 76
92 1
49 18
44 27
55 34
23 34
90 76
72 62
59 31
42 31
53 90
23 37
37 53
84 59
72 57
21 23
24 85
84 43
1 37
77 74
15 27
71 57
28 68
99 84
27 23
15 5
29 82
96 83
69 33
22 85
62 6
89 3
54 53
99 38
9 84
26 77
14 89
18 40
38 62
51 68
20 7
85 70
45 27
93 12
93 62
9 89
35 69
52 85
13 13
12 64
58 72
95 69
86 14
82 76
55 4
72 65
11 75
89 62
9 17
19 46
32 52
80 28
83 57
47 48
76 30
13 88
92 71
19 47
14 43
48 22
27 63
74 51
33 43
14 12
8 33
39 16
88 61
9 64
49 17
6 86
75 52
31 10
96 54
43 62
66 40
79 30
99 37
30 58
34 7
42 59
38 8
91 44
95 81
24 88
96 36
90 80
49 49
44 54
64 50
87 48
51 73
66 12
55 5
78 8
37 47
28 27
95 84
34 76
43 88
83 18
46 25
33 19
9 20
37 86
84 67
7 73
96 76
26 58
5 18
1 48
70 77
96 59
12 84
96 17
2 28
5 1
93 58
68 12
41 3
10 80
58 36
66 33
87 3
63 57
60 84
42 89
84 83
24 82
16 10
32 80
38 71
25 47
74 38
2 33
65 65
44 31
81 76
77 78
12 8
10
80 80
15 57
41 32
7 11
76 34
22 52
45 5
74 24
15 66
80 2
45 1
7 3
20
99 1
67 1
61 1
89 1
27 1
34 1
12 1
36 1
45 1
88 1
68 1
82 1
49 1
86 1
83 1
58 1
47 1
16 1
95 1
33 1
60 1
10 1
20
1 99
1 27
1 23
1 66
1 64
1 77
1 74
1 79
1 25
1 82
1 67
1 86
1 51
1 38
1 42
1 30
1 19
1 78
1 33
1 36
1 95
1 12
160
72 72
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
3 17
3 18
3 19
3 20
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
4 14
4 15
4 16
4 17
4 18
4 19
4 20
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
5 14
5 15
5 16
5 17
5 18
5 19
5 20
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
6 16
6 17
6 18
6 19
6 20
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
7 10
7 11
7 12
7 13
7 14
7 15
7 16
7 17
7 18
7 19
7 20
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
8 9
8 10
8 11
8 12
8 13
8 14
8 15
8 16
8 17
8 18
8 19
8 20
8 20
266
63 81
1 68
1 69
1 70
1 71
1 72
1 73
1 74
1 75
1 76
1 77
1 78
1 79
1 80
1 81
2 68
2 69
2 70
2 71
2 72
2 73
2 74
2 75
2 76
2 77
2 78
2 79
2 80
2 81
3 68
3 69
3 70
3 71
3 72
3 73
3 74
3 75
3 76
3 77
3 78
3 79
3 80
3 81
4 68
4 69
4 70
4 71
4 72
4 73
4 74
4 75
4 76
4 77
4 78
4 79
4 80
4 81
5 68
5 69
5 70
5 71
5 72
5 73
5 74
5 75
5 76
5 77
5 78
5 79
5 80
5 81
6 68
6 69
6 70
6 71
6 72
6 73
6 74
6 75
6 76
6 77
6 78
6 79
6 80
6 81
7 68
7 69
7 70
7 71
7 72
7 73
7 74
7 75
7 76
7 77
7 78
7 79
7 80
7 81
8 68
8 69
8 70
8 71
8 72
8 73
8 74
8 75
8 76
8 77
8 78
8 79
8 80
8 81
9 68
9 69
9 70
9 71
9 72
9 73
9 74
9 75
9 76
9 77
9 78
9 79
9 80
9 81
10 68
10 69
10 70
10 71
10 72
10 73
10 74
10 75
10 76
10 77
10 78
10 79
10 80
10 81
11 68
11 69
11 70
11 71
11 72
11 73
11 74
11 75
11 76
11 77
11 78
11 79
11 80
11 81
12 68
12 69
12 70
12 71
12 72
12 73
12 74
12 75
12 76
12 77
12 78
12 79
12 80
12 81
13 68
13 69
13 70
13 71
13 72
13 73
13 74
13 75
13 76
13 77
13 78
13 79
13 80
13 81
14 68
14 69
14 70
14 71
14 72
14 73
14 74
14 75
14 76
14 77
14 78
14 79
14 80
14 81
15 68
15 69
15 70
15 71
15 72
15 73
15 74
15 75
15 76
15 77
15 78
15 79
15 80
15 81
16 68
16 69
16 70
16 71
16 72
16 73
16 74
16 75
16 76
16 77
16 78
16 79
16 80
16 81
17 68
17 69
17 70
17 71
17 72
17 73
17 74
17 75
17 76
17 77
17 78
17 79
17 80
17 81
18 68
18 69
18 70
18 71
18 72
18 73
18 74
18 75
18 76
18 77
18 78
18 79
18 80
18 81
19 68
19 69
19 70
19 71
19 72
19 73
19 74
19 75
19 76
19 77
19 78
19 79
19 80
19 81
19 14
104
54 9
42 1
42 2
42 3
42 4
42 5
42 6
42 7
42 8
43 1
43 2
43 3
43 4
43 5
43 6
43 7
43 8
44 1
44 2
44 3
44 4
44 5
44 6
44 7
44 8
45 1
45 2
45 3
45 4
45 5
45 6
45 7
45 8
46 1
46 2
46 3
46 4
46 5
46 6
46 7
46 8
47 1
47 2
47 3
47 4
47 5
47 6
47 7
47 8
48 1
48 2
48 3
48 4
48 5
48 6
48 7
48 8
49 1
49 2
49 3
49 4
49 5
49 6
49 7
49 8
50 1
50 2
50 3
50 4
50 5
50 6
50 7
50 8
51 1
51 2
51 3
51 4
51 5
51 6
51 7
51 8
52 1
52 2
52 3
52 4
52 5
52 6
52 7
52 8
53 1
53 2
53 3
53 4
53 5
53 6
53 7
53 8
54 1
54 2
54 3
54 4
54 5
54 6
54 7
54 8
13 8
91
54 90
42 84
42 85
42 86
42 87
42 88
42 89
42 90
43 84
43 85
43 86
43 87
43 88
43 89
43 90
44 84
44 85
44 86
44 87
44 88
44 89
44 90
45 84
45 85
45 86
45 87
45 88
45 89
45 90
46 84
46 85
46 86
46 87
46 88
46 89
46 90
47 84
47 85
47 86
47 87
47 88
47 89
47 90
48 84
48 85
48 86
48 87
48 88
48 89
48 90
49 84
49 85
49 86
49 87
49 88
49 89
49 90
50 84
50 85
50 86
50 87
50 88
50 89
50 90
51 84
51 85
51 86
51 87
51 88
51 89
51 90
52 84
52 85
52 86
52 87
52 88
52 89
52 90
53 84
53 85
53 86
53 87
53 88
53 89
53 90
54 84
54 85
54 86
54 87
54 88
54 89
54 90
13 7
42
54 27
2 2
2 3
2 4
2 5
2 6
2 7
3 2
3 3
3 4
3 5
3 6
3 7
4 2
4 3
4 4
4 5
4 6
4 7
5 2
5 3
5 4
5 5
5 6
5 7
6 2
6 3
6 4
6 5
6 6
6 7
7 2
7 3
7 4
7 5
7 6
7 7
8 2
8 3
8 4
8 5
8 6
8 7
7 6
40
54 36
2 31
2 32
2 33
2 34
2 35
3 31
3 32
3 33
3 34
3 35
4 31
4 32
4 33
4 34
4 35
5 31
5 32
5 33
5 34
5 35
6 31
6 32
6 33
6 34
6 35
7 31
7 32
7 33
7 34
7 35
8 31
8 32
8 33
8 34
8 35
9 31
9 32
9 33
9 34
9 35
8 5
187
54 36
37 2
37 3
37 4
37 5
37 6
37 7
37 8
37 9
37 10
37 11
37 12
38 2
38 3
38 4
38 5
38 6
38 7
38 8
38 9
38 10
38 11
38 12
39 2
39 3
39 4
39 5
39 6
39 7
39 8
39 9
39 10
39 11
39 12
40 2
40 3
40 4
40 5
40 6
40 7
40 8
40 9
40 10
40 11
40 12
41 2
41 3
41 4
41 5
41 6
41 7
41 8
41 9
41 10
41 11
41 12
42 2
42 3
42 4
42 5
42 6
42 7
42 8
42 9
42 10
42 11
42 12
43 2
43 3
43 4
43 5
43 6
43 7
43 8
43 9
43 10
43 11
43 12
44 2
44 3
44 4
44 5
44 6
44 7
44 8
44 9
44 10
44 11
44 12
45 2
45 3
45 4
45 5
45 6
45 7
45 8
45 9
45 10
45 11
45 12
46 2
46 3
46 4
46 5
46 6
46 7
46 8
46 9
46 10
46 11
46 12
47 2
47 3
47 4
47 5
47 6
47 7
47 8
47 9
47 10
47 11
47 12
48 2
48 3
48 4
48 5
48 6
48 7
48 8
48 9
48 10
48 11
48 12
49 2
49 3
49 4
49 5
49 6
49 7
49 8
49 9
49 10
49 11
49 12
50 2
50 3
50 4
50 5
50 6
50 7
50 8
50 9
50 10
50 11
50 12
51 2
51 3
51 4
51 5
51 6
51 7
51 8
51 9
51 10
51 11
51 12
52 2
52 3
52 4
52 5
52 6
52 7
52 8
52 9
52 10
52 11
52 12
53 2
53 3
53 4
53 5
53 6
53 7
53 8
53 9
53 10
53 11
53 12
17 11
266
54 36
35 22
35 23
35 24
35 25
35 26
35 27
35 28
35 29
35 30
35 31
35 32
35 33
35 34
35 35
36 22
36 23
36 24
36 25
36 26
36 27
36 28
36 29
36 30
36 31
36 32
36 33
36 34
36 35
37 22
37 23
37 24
37 25
37 26
37 27
37 28
37 29
37 30
37 31
37 32
37 33
37 34
37 35
38 22
38 23
38 24
38 25
38 26
38 27
38 28
38 29
38 30
38 31
38 32
38 33
38 34
38 35
39 22
39 23
39 24
39 25
39 26
39 27
39 28
39 29
39 30
39 31
39 32
39 33
39 34
39 35
40 22
40 23
40 24
40 25
40 26
40 27
40 28
40 29
40 30
40 31
40 32
40 33
40 34
40 35
41 22
41 23
41 24
41 25
41 26
41 27
41 28
41 29
41 30
41 31
41 32
41 33
41 34
41 35
42 22
42 23
42 24
42 25
42 26
42 27
42 28
42 29
42 30
42 31
42 32
42 33
42 34
42 35
43 22
43 23
43 24
43 25
43 26
43 27
43 28
43 29
43 30
43 31
43 32
43 33
43 34
43 35
44 22
44 23
44 24
44 25
44 26
44 27
44 28
44 29
44 30
44 31
44 32
44 33
44 34
44 35
45 22
45 23
45 24
45 25
45 26
45 27
45 28
45 29
45 30
45 31
45 32
45 33
45 34
45 35
46 22
46 23
46 24
46 25
46 26
46 27
46 28
46 29
46 30
46 31
46 32
46 33
46 34
46 35
47 22
47 23
47 24
47 25
47 26
47 27
47 28
47 29
47 30
47 31
47 32
47 33
47 34
47 35
48 22
48 23
48 24
48 25
48 26
48 27
48 28
48 29
48 30
48 31
48 32
48 33
48 34
48 35
49 22
49 23
49 24
49 25
49 26
49 27
49 28
49 29
49 30
49 31
49 32
49 33
49 34
49 35
50 22
50 23
50 24
50 25
50 26
50 27
50 28
50 29
50 30
50 31
50 32
50 33
50 34
50 35
51 22
51 23
51 24
51 25
51 26
51 27
51 28
51 29
51 30
51 31
51 32
51 33
51 34
51 35
52 22
52 23
52 24
52 25
52 26
52 27
52 28
52 29
52 30
52 31
52 32
52 33
52 34
52 35
53 22
53 23
53 24
53 25
53 26
53 27
53 28
53 29
53 30
53 31
53 32
53 33
53 34
53 35
19 14
0

persimmons.py

# -*- coding: utf-8 -*-


def max_persimmons(field_size, trees, estate_size):
    rv = 0
    field_w, field_h = field_size
    estate_w, estate_h = estate_size
    corner_x = 1
    corner_y = 1
    last_x = field_w - estate_w + 1
    last_y = field_h - estate_h + 1
    max_possible_matches = estate_h * estate_w
    while True:
        if corner_x > last_x:
            corner_y += 1
            if corner_y > last_y:
                break
            corner_x = 1
        matched = 0
        max_x = corner_x + estate_w - 1
        max_y = corner_y + estate_h - 1
        skip_right = estate_w
        for x, y in trees:
            if corner_x <= x <= max_x and corner_y <= y <= max_y:
                matched += 1
                if x != corner_x:
                    skip_right = min(skip_right, x - corner_x)
        # it can not be bigger
        if matched == max_possible_matches:
            return matched
        if matched > rv:
            rv = matched
        corner_x += skip_right
    return rv


if __name__ == '__main__':
    trees = set((
        (2, 2),
        (2, 5),
        (2, 7),
        (3, 3),
        (3, 8),
        (4, 2),
        (4, 5),
        (4, 8),
        (6, 4),
        (6, 7),
        (7, 5),
        (7, 8),
        (8, 1),
        (8, 4),
        (9, 6),
        (10, 3),
    ))
    assert max_persimmons((10, 8), trees, (4, 3)) == 4

    trees = set((
        (1, 2),
        (2, 1),
        (2, 4),
        (3, 4),
        (4, 2),
        (5, 3),
        (6, 1),
        (6, 2),
    ))
    assert max_persimmons((6, 4), trees, (3, 2)) == 3

    with open('B1.txt') as f:
        data = f.readlines()
    trees = []
    for line in data:
        if line == '0\n':
            break
        if ' ' in line:
            trees.append(tuple(map(int, line.strip().split())))
        elif trees:
            field_size, estate_size = trees.pop(0), trees.pop()
            print field_size, estate_size, len(trees)
            max = max_persimmons(field_size, set(trees), estate_size)
            assert max <= estate_size[0] * estate_size[1]
            print max
            trees = []