uva696測資A

Input:
2 3
5 5
4 7
1 10
10 1
2 10
10 2
3 4
4 3
3 5
5 3
3 6
3 2
7 4
6 6
5 6
1 24
2 140
2 390
3 58
4 84
4 301
5 29
5 82
5 162
6 4
7 108
11 426
12 18
12 377
53 8
57 455
58 18
106 461
269 369
320 16
390 460
499 499
500 1
500 2
500 3
500 500
0 0
Output:
4 knights may be placed on a 2 row 3 column board.
13 knights may be placed on a 5 row 5 column board.
14 knights may be placed on a 4 row 7 column board.
10 knights may be placed on a 1 row 10 column board.
10 knights may be placed on a 10 row 1 column board.
12 knights may be placed on a 2 row 10 column board.
12 knights may be placed on a 10 row 2 column board.
6 knights may be placed on a 3 row 4 column board.
6 knights may be placed on a 4 row 3 column board.
8 knights may be placed on a 3 row 5 column board.
8 knights may be placed on a 5 row 3 column board.
9 knights may be placed on a 3 row 6 column board.
4 knights may be placed on a 3 row 2 column board.
14 knights may be placed on a 7 row 4 column board.
18 knights may be placed on a 6 row 6 column board.
15 knights may be placed on a 5 row 6 column board.
24 knights may be placed on a 1 row 24 column board.
140 knights may be placed on a 2 row 140 column board.
392 knights may be placed on a 2 row 390 column board.
87 knights may be placed on a 3 row 58 column board.
168 knights may be placed on a 4 row 84 column board.
602 knights may be placed on a 4 row 301 column board.
73 knights may be placed on a 5 row 29 column board.
205 knights may be placed on a 5 row 82 column board.
405 knights may be placed on a 5 row 162 column board.
12 knights may be placed on a 6 row 4 column board.
378 knights may be placed on a 7 row 108 column board.
2343 knights may be placed on a 11 row 426 column board.
108 knights may be placed on a 12 row 18 column board.
2262 knights may be placed on a 12 row 377 column board.
212 knights may be placed on a 53 row 8 column board.
12968 knights may be placed on a 57 row 455 column board.
522 knights may be placed on a 58 row 18 column board.
24433 knights may be placed on a 106 row 461 column board.
49631 knights may be placed on a 269 row 369 column board.
2560 knights may be placed on a 320 row 16 column board.
89700 knights may be placed on a 390 row 460 column board.
124501 knights may be placed on a 499 row 499 column board.
500 knights may be placed on a 500 row 1 column board.
500 knights may be placed on a 500 row 2 column board.
750 knights may be placed on a 500 row 3 column board.
125000 knights may be placed on a 500 row 500 column board.