2022 CSP-J 第二轮 T4｜上升点列

一、完整题目

题目描述

在二维平面上，一个点列 (x₁,y₁),(x₂,y₂),…,(xₘ,yₘ) 被称为上升点列，当且仅当对每个 1≤i<m，都有：

也就是说，从点列中的一个点走到下一个点时，只能向右走一个单位或向上走一个单位。

现在给定平面上的 n 个互不相同的整点。你还可以在平面上任意添加 k 个整点。请从给定点和新增点中选出尽可能多的点，并按合适顺序组成一个上升点列，求这个点列的最大长度。

输入格式

从文件 point.in 中读入数据。

第一行包含两个正整数 n,k，分别表示原有点的数量和可以新增的点数。

接下来 n 行，每行包含两个正整数 xᵢ,yᵢ，表示一个给定点。所有给定点互不相同。

输出格式

输出到文件 point.out 中。

输出一行一个整数，表示能够得到的上升点列的最大长度。

样例 1

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

8

例如可以在 (4,3) 和 (5,4) 处补点，把更多原有点连接进同一条上升点列，最终长度为 8。

样例 2

4 100
10 10
15 25
20 20
30 30

103

数据范围与测试点

所有数据保证 1≤n≤500，0≤k≤100，1≤xᵢ,yᵢ≤10^9，给定点两两不同。