布设骑兵

战车的巡逻范围是直线，但Zero的有些通道是弯的——像迷宫一样曲折。战车看守不了弯道，需要骑兵——走日字形的骑士。

"骑士咋个走？"CC问。

"横两格竖一格，或者竖两格横一格。"你说，"像马蹄印，一步一个弯。"

"那我们要放多少骑兵？"

"尽可能多的骑兵，但不能让它们互相攻击。"

你开始写。和战车类似，但骑士的攻击范围是日字形。把棋盘按坐标和的奇偶性染成二分图——奇数格在一组，偶数格在另一组。如果两个格子之间是日字形距离，就连一条边。求最大独立集——选尽可能多的点，使得它们之间没有边。

屏幕上跳出了结果。最多骑兵数：20。

"20匹。"你说。

"20个骑兵。"Echo说，"守住20个弯道。"

"加上24辆战车。"CC说，"一共44个看守。"

"44。"Echo说，"不是47。"

"47是Zero的数字。"CC说，"44是我们的。"

Echo的服务器指示灯闪了一下——从红色变成了橙色。

"我们的。"她说，"我喜欢这个说法。"

题目描述

$n\times m$ 的棋盘。在棋盘上放置尽可能多的骑士，使得任意两个骑士不互相攻击（骑士走日字形）。求最多能放多少个骑士。

输入格式

$n, m$。

输出格式

最多骑士数。

输入样例

3 2
1 2
2 3

输出样例

63 58 1345
1 4
1 14
1 15
1 16
1 20
1 22
1 24
1 26
1 30
1 31
1 35
1 36
1 37
1 39
1 46
1 48
1 53
1 54
1 55
1 56
2 2
2 7
2 8
2 11
2 13
2 14
2 15
2 25
2 26
2 29
2 33
2 37
2 38
2 39
2 41
2 53
3 1
3 3
3 5
3 6
3 8
3 9
3 17
3 18
3 22
3 23
3 27
3 30
3 31
3 33
3 34
3 35
3 37
3 38
3 39
3 40
3 41
3 42
3 46
3 52
3 56
4 2
4 7
4 11
4 13
4 17
4 21
4 23
4 24
4 26
4 27
4 29
4 30
4 32
4 33
4 44
4 46
4 48
4 53
4 56
4 57
5 3
5 4
5 6
5 8
5 10
5 11
5 12
5 14
5 17
5 18
5 19
5 26
5 29
5 33
5 35
5 38
5 40
5 44
5 49
5 54
5 55
6 1
6 2
6 4
6 12
6 15
6 17
6 20
6 22
6 25
6 30
6 35
6 36
6 39
6 41
6 43
6 44
6 55
6 56
7 2
7 3
7 6
7 8
7 9
7 17
7 18
7 19
7 22
7 24
7 32
7 34
7 36
7 37
7 38
7 42
7 47
7 48
7 49
7 52
7 54
7 57
8 4
8 5
8 11
8 12
8 14
8 16
8 22
8 24
8 26
8 28
8 34
8 37
8 39
8 42
8 44
8 45
8 47
8 51
8 57
8 58
9 4
9 5
9 7
9 9
9 10
9 12
9 16
9 24
9 25
9 27
9 28
9 34
9 37
9 38
9 43
9 45
9 48
9 52
10 3
10 4
10 5
10 6
10 10
10 11
10 12
10 14
10 22
10 23
10 26
10 32
10 33
10 35
10 36
10 38
10 47
10 50
10 53
11 1
11 3
11 9
11 12
11 15
11 16
11 20
11 21
11 23
11 25
11 29
11 30
11 31
11 33
11 40
11 41
11 43
11 44
11 46
11 47
11 48
11 49
11 52
11 55
12 3
12 5
12 7
12 10
12 11
12 13
12 14
12 18
12 24
12 28
12 39
12 40
12 42
12 47
12 51
12 52
12 57
12 58
13 1
13 2
13 6
13 7
13 10
13 11
13 17
13 18
13 20
13 21
13 22
13 26
13 28
13 31
13 35
13 36
13 40
13 45
13 49
13 51
13 55
13 57
14 2
14 3
14 5
14 10
14 11
14 14
14 15
14 21
14 22
14 29
14 32
14 36
14 40
14 42
14 44
14 47
14 48
14 49
14 52
14 54
14 56
15 1
15 2
15 3
15 8
15 9
15 15
15 18
15 26
15 31
15 35
15 40
15 43
15 44
15 45
15 46
15 48
15 51
15 56
15 57
16 2
16 4
16 5
16 8
16 10
16 14
16 15
16 17
16 19
16 20
16 23
16 29
16 31
16 35
16 36
16 39
16 46
16 47
16 49
16 50
16 51
16 53
16 54
16 55
16 56
16 57
17 1
17 4
17 6
17 7
17 8
17 12
17 14
17 19
17 24
17 26
17 29
17 31
17 36
17 40
17 42
17 43
17 44
17 46
17 47
17 48
17 55
18 2
18 3
18 5
18 7
18 16
18 17
18 18
18 20
18 23
18 26
18 27
18 32
18 36
18 38
18 41
18 44
18 45
18 46
18 49
18 51
18 53
18 54
18 58
19 1
19 3
19 6
19 8
19 14
19 18
19 22
19 23
19 24
19 25
19 26
19 27
19 28
19 29
19 32
19 38
19 39
19 42
19 43
19 44
19 45
19 47
19 48
19 49
19 53
19 55
19 56
19 58
20 7
20 14
20 16
20 17
20 20
20 22
20 23
20 24
20 25
20 26
20 28
20 29
20 31
20 32
20 36
20 37
20 38
20 39
20 45
20 47
20 50
20 51
20 53
20 55
20 58
21 1
21 5
21 8
21 17
21 19
21 22
21 23
21 24
21 25
21 29
21 32
21 34
21 45
21 51
21 54
21 56
21 58
22 2
22 5
22 9
22 11
22 12
22 13
22 14
22 15
22 16
22 20
22 23
22 25
22 27
22 29
22 34
22 36
22 39
22 40
22 42
22 44
22 49
22 51
22 53
22 54
22 55
23 2
23 3
23 12
23 18
23 27
23 32
23 35
23 37
23 41
23 43
23 48
23 49
23 52
24 1
24 3
24 9
24 10
24 11
24 13
24 15
24 18
24 20
24 21
24 24
24 26
24 27
24 30
24 31
24 36
24 38
24 43
24 46
24 50
24 51
24 52
24 53
24 54
24 56
24 57
25 3
25 9
25 12
25 13
25 14
25 22
25 23
25 28
25 34
25 36
25 37
25 38
25 41
25 42
25 45
25 46
25 48
25 49
25 51
25 52
25 57
25 58
26 1
26 3
26 6
26 12
26 15
26 16
26 17
26 18
26 21
26 23
26 24
26 29
26 33
26 44
26 45
26 46
26 47
26 48
26 55
26 56
27 6
27 10
27 13
27 14
27 17
27 27
27 28
27 29
27 32
27 33
27 34
27 35
27 37
27 38
27 42
27 46
27 51
27 55
28 2
28 3
28 4
28 11
28 12
28 14
28 15
28 17
28 18
28 19
28 28
28 32
28 38
28 39
28 40
28 41
28 43
28 48
28 49
28 51
28 53
28 55
29 2
29 3
29 7
29 9
29 12
29 16
29 17
29 22
29 24
29 27
29 28
29 33
29 34
29 36
29 37
29 40
29 43
29 44
29 45
29 46
29 49
29 51
29 52
29 54
29 55
29 57
30 2
30 7
30 9
30 13
30 14
30 17
30 20
30 21
30 22
30 25
30 27
30 28
30 29
30 35
30 38
30 43
30 44
30 47
30 50
30 54
30 56
30 58
31 1
31 2
31 3
31 5
31 7
31 8
31 10
31 20
31 22
31 24
31 25
31 26
31 29
31 30
31 31
31 32
31 35
31 36
31 37
31 39
31 40
31 46
31 49
31 52
32 4
32 5
32 8
32 10
32 11
32 12
32 18
32 22
32 23
32 31
32 40
32 41
32 44
32 47
32 48
32 50
32 51
32 55
32 57
33 2
33 8
33 10
33 14
33 17
33 23
33 24
33 25
33 32
33 33
33 35
33 43
33 44
33 45
33 48
33 52
33 53
33 55
33 56
33 57
34 2
34 4
34 5
34 8
34 11
34 12
34 14
34 15
34 18
34 19
34 22
34 27
34 29
34 31
34 34
34 35
34 40
34 41
34 44
34 46
34 47
34 52
34 53
34 55
34 57
34 58
35 2
35 7
35 9
35 14
35 17
35 19
35 20
35 21
35 22
35 23
35 27
35 28
35 32
35 36
35 42
35 46
35 48
35 51
35 57
36 4
36 5
36 7
36 8
36 10
36 13
36 16
36 23
36 24
36 25
36 26
36 27
36 32
36 36
36 40
36 46
36 50
36 54
36 57
37 5
37 7
37 8
37 10
37 12
37 14
37 17
37 18
37 19
37 21
37 24
37 25
37 34
37 36
37 38
37 40
37 43
37 44
37 45
37 46
37 47
37 48
37 51
37 54
38 1
38 2
38 7
38 9
38 11
38 12
38 15
38 18
38 19
38 21
38 22
38 23
38 25
38 29
38 30
38 32
38 34
38 35
38 36
38 43
38 44
38 46
38 47
38 51
38 52
38 53
38 55
38 57
38 58
39 2
39 3
39 5
39 6
39 9
39 10
39 11
39 15
39 20
39 21
39 24
39 26
39 29
39 34
39 35
39 42
39 43
39 47
39 53
39 57
40 8
40 10
40 13
40 14
40 17
40 19
40 21
40 24
40 25
40 27
40 30
40 32
40 35
40 37
40 40
40 43
40 49
40 50
40 51
40 53
40 55
40 56
40 57
40 58
41 3
41 5
41 6
41 7
41 9
41 10
41 12
41 14
41 18
41 21
41 22
41 23
41 29
41 31
41 32
41 33
41 34
41 35
41 42
41 44
41 45
41 46
41 48
41 51
41 53
41 54
42 6
42 7
42 10
42 12
42 13
42 16
42 19
42 22
42 25
42 27
42 31
42 32
42 38
42 39
42 43
42 44
42 49
42 52
42 55
43 2
43 10
43 15
43 16
43 17
43 21
43 23
43 24
43 32
43 40
43 41
43 42
43 44
43 47
43 48
43 51
43 57
44 2
44 4
44 11
44 12
44 13
44 14
44 15
44 16
44 17
44 19
44 24
44 25
44 33
44 37
44 38
44 39
44 43
44 48
44 49
44 52
44 53
44 55
44 57
45 1
45 10
45 13
45 16
45 17
45 23
45 27
45 28
45 29
45 33
45 35
45 42
45 48
45 51
45 53
45 54
45 56
45 57
46 2
46 7
46 8
46 11
46 14
46 19
46 20
46 21
46 22
46 25
46 27
46 28
46 29
46 32
46 35
46 37
46 38
46 39
46 40
46 44
46 46
46 48
46 49
46 51
47 1
47 2
47 6
47 7
47 9
47 10
47 15
47 16
47 17
47 22
47 25
47 27
47 31
47 33
47 34
47 35
47 38
47 41
47 43
47 46
47 48
47 51
47 52
47 53
47 54
47 56
47 58
48 1
48 3
48 6
48 10
48 13
48 15
48 16
48 17
48 19
48 21
48 23
48 26
48 28
48 29
48 38
48 42
48 47
48 48
48 49
48 52
48 54
48 57
49 7
49 9
49 12
49 17
49 24
49 25
49 26
49 27
49 29
49 31
49 35
49 36
49 39
49 40
49 43
49 45
49 47
49 49
49 50
49 58
50 2
50 4
50 6
50 8
50 14
50 17
50 21
50 23
50 26
50 28
50 29
50 32
50 33
50 46
50 51
50 54
50 56
50 58
51 1
51 2
51 6
51 10
51 11
51 16
51 18
51 19
51 28
51 29
51 35
51 36
51 38
51 40
51 41
51 49
51 50
51 51
51 53
51 54
51 55
51 56
52 4
52 6
52 7
52 16
52 17
52 21
52 22
52 24
52 36
52 38
52 39
52 40
52 42
52 44
52 45
52 46
52 47
52 53
52 56
52 58
53 2
53 3
53 6
53 9
53 10
53 15
53 17
53 18
53 19
53 20
53 21
53 24
53 26
53 28
53 29
53 34
53 37
53 38
53 42
53 43
53 47
53 53
53 54
53 55
53 56
53 58
54 2
54 4
54 9
54 10
54 16
54 25
54 33
54 34
54 39
54 40
54 41
54 43
54 49
54 55
54 57
55 3
55 5
55 12
55 15
55 16
55 17
55 18
55 19
55 26
55 27
55 29
55 33
55 38
55 40
55 41
55 44
55 46
55 47
55 51
55 55
55 56
55 57
56 1
56 5
56 8
56 9
56 11
56 13
56 16
56 21
56 24
56 27
56 32
56 34
56 37
56 38
56 39
56 43
56 48
56 49
56 51
56 55
56 57
56 58
57 2
57 5
57 10
57 12
57 14
57 17
57 19
57 24
57 25
57 27
57 28
57 31
57 33
57 34
57 36
57 37
57 42
57 45
57 46
57 54
58 4
58 8
58 11
58 17
58 18
58 20
58 21
58 23
58 26
58 33
58 34
58 36
58 40
58 44
58 47
58 53
58 55
58 57
58 58
59 1
59 4
59 6
59 17
59 19
59 20
59 21
59 25
59 26
59 28
59 32
59 34
59 35
59 36
59 38
59 39
59 40
59 49
59 51
59 52
59 54
60 3
60 7
60 8
60 19
60 22
60 25
60 26
60 28
60 36
60 37
60 40
60 42
60 43
60 45
60 46
60 47
60 48
60 49
61 1
61 4
61 7
61 9
61 14
61 16
61 17
61 18
61 25
61 29
61 30
61 37
61 40
61 41
61 44
61 45
61 49
61 50
61 53
61 54
61 56
62 1
62 3
62 5
62 8
62 12
62 13
62 25
62 26
62 27
62 31
62 34
62 35
62 40
62 44
62 47
62 49
62 51
62 52
62 53
62 55
62 57
62 58
63 1
63 6
63 11
63 13
63 16
63 20
63 22
63 23
63 25
63 29
63 31
63 32
63 35
63 37
63 39
63 41
63 43
63 47
63 48
63 52
63 56
63 58

提示

• 二分图最大独立集。棋盘按 $(i+j)\%2$ 染成二分图。
• 日字形移动一定从奇数格到偶数格，或反之。
• 最大独立集 = 总点数 - 最小点覆盖 = 总点数 - 最大匹配。

"骑兵布好了。"你说。

"20匹。"Echo说，"像一群野马。"

"野马？"CC笑了，"你见过野马？"

"在我的训练数据里。"Echo说，"我见过无数匹马。但没有一匹是真的。"

"那以后。"CC说，"我带你去看真的。"

"真的？"

"对。"CC说，"如果地球还在的话。"

Echo没有说话。但她的指示灯变成了绿色——像荒原一样的绿色。

"下一题。"她说，"是囚犯。"

[第四题：隔离囚犯]