2022 T4 上升点列

主知识点：动态规划。交叉标签：动态规划、排序、深搜。
暴力标注：DP 可用暴力拿部分分。
OJ 使用标准输入与标准输出。原比赛文件名为 point.in / point.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 512 MiB；测试点 20；总分 100。
数据来源：公开存档数据；未逐文件对照官网下载包。

题目描述

二维平面有 $n$ 个互不相同的整数点，可另外添加 $k$ 个整数点，添加点的坐标不受限制。在这些点中选出一个序列，相邻点必须恰好向右一格或向上一格。求这样的序列的最大点数。

输入格式

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

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

输出格式

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

样例

样例 1

输入：

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

输出：

8

样例 2

输入：

4 100
10 10
15 25
20 20
30 30

输出：

103

数据范围与特殊性质

保证对于所有数据满足：$1 \leq n \leq 500$，$0 \leq k \leq 100$。对于所有给定的整点，其横纵坐标 $1 \leq x_i, y_i \leq {10}^9$，且保证所有给定的点互不重合。对于自由添加的整点，其横纵坐标不受限制。

测试点编号	$n \leq$	$k \leq$	$x_i,y_i \leq$
$1 \sim 2$	$10$	$0$	$10$
$3 \sim 4$		$100$	$100$
$5 \sim 7$	$500$	$0$
$8 \sim 10$			${10}^9$
$11 \sim 15$		$100$	$100$
$16 \sim 20$			${10}^9$

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

暴力退路标注（教学补充）

DP 可用暴力拿部分分。n≤10 时枚举原有点子集，将选点按坐标排序，检查坐标单调，累加相邻曼哈顿距离减 1 的插点花费；若不超过 k，则序列长为选中原有点数+k。可面向 1~4 点。剩余插点可以加在链首尾。

目标范围：20 分（1~4 点）。部分分按原题规模判断，不构成对任意实现或评测机的得分保证。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P8816
• 赛事：CSP-J 第二轮入门级 2022。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。