开始 2022-11-07 00:00:00

2022真题

结束 2022-11-10 18:40:00
比赛已经结束
当前 2024-11-20 00:37:47

D. 上升点列（point)

描述

在一个二维平面内，给定n个整数点(x_i,y_i)，此外你还可以自由添加k个整数点。

你在自由添加k个点后，还需要从n+k个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为1而且横坐标、纵坐标值均单调不减，即：

x_{i+1} - x_i = 1

y_{i+1} = y_i

或

x_{i+1} = x_i

y_{i+1} - y_i = 1

请给出满足条件的序列的最大长度。

输入

第一行，两个正整数n,k分别表示给定的整数点个数、可自由添加的整数点个数。

接下来n行，第i行两个正整数x_i,y_i表示给定的第i个点的横纵坐标。

输出

输出一个整数表示满足条件的序列的最大长度。

样例

输入

8 2
3 1
3 2
3 3
3 6
1 2
2 2
5 5
5 3

输出

8

输入

4 100
10 10
15 25
20 20
30 30

输出

103

输入

100 0
4 2
14 2
4 13
2 6
3 7
1 7
4 18
4 9
13 8
4 20
1 3
13 5
21 6
9 4
26 7
16 3
12 3
4 3
1 4
2 21
1 5
2 3
10 3
1 12
15 12
3 2
16 1
11 3
3 1
2 1
2 4
12 19
2 14
5 10
1 8
9 6
7 5
4 11
11 8
21 10
1 17
4 1
21 13
4 7
5 4
2 10
1 9
7 3
6 2
5 1
2 16
6 10
3 16
7 2
6 1
8 6
5 3
6 4
2 2
12 2
10 13
8 15
10 4
3 3
2 7
2 5
25 9
3 15
10 1
3 4
3 5
1 1
9 1
9 2
11 4
15 3
11 28
12 1
8 8
20 5
7 8
6 3
5 2
14 1
10 2
14 14
8 4
1 2
8 10
9 18
7 1
9 5
29 20
15 15
1 28
23 20
5 24
1 10
1 11
35 2

输出

10

提示

提交

登录

注册
时间限制 1000 毫秒
内存限制 128 MB
提交