311108: CF1935C. Messenger in MAC
Description
In the new messenger for the students of the Master's Assistance Center, Keftemerum, an update is planned, in which developers want to optimize the set of messages shown to the user. There are a total of $n$ messages. Each message is characterized by two integers $a_i$ and $b_i$. The time spent reading the set of messages with numbers $p_1, p_2, \ldots, p_k$ ($1 \le p_i \le n$, all $p_i$ are distinct) is calculated by the formula:
$$\Large \sum_{i=1}^{k} a_{p_i} + \sum_{i=1}^{k - 1} |b_{p_i} - b_{p_{i+1}}|$$
Note that the time to read a set of messages consisting of one message with number $p_1$ is equal to $a_{p_1}$. Also, the time to read an empty set of messages is considered to be $0$.
The user can determine the time $l$ that he is willing to spend in the messenger. The messenger must inform the user of the maximum possible size of the set of messages, the reading time of which does not exceed $l$. Note that the maximum size of the set of messages can be equal to $0$.
The developers of the popular messenger failed to implement this function, so they asked you to solve this problem.
InputEach test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $n$ and $l$ ($1 \leq n \leq 2000$, $1 \leq l \leq 10^9$) — the number of messages and the time the user is willing to spend in the messenger.
The $i$-th of the next $n$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^9$) — characteristics of the $i$-th message.
It is guaranteed that the sum of $n^2$ over all test cases does not exceed $4 \cdot 10^6$.
OutputFor each test case, output a single integer — the maximum possible size of a set of messages, the reading time of which does not exceed $l$.
ExampleInput5 5 8 4 3 1 5 2 4 4 3 2 3 1 6 4 10 3 12 4 8 2 1 2 12 5 26 24 7 8 28 30 22 3 8 17 17 5 14 15 3 1000000000 998244353 179 239 228 1337 993 1007Output
3 1 2 1 0Note
In the first test case, you can take a set of three messages with numbers $p_1 = 3$, $p_2 = 2$, and $p_3 = 5$. The time spent reading this set is equal to $a_3 + a_2 + a_5 + |b_3 - b_2| + |b_2 - b_5| = 2 + 1 + 2 + |4 - 5| + |5 - 3| = 8$.
In the second test case, you can take a set of one message with number $p_1 = 1$. The time spent reading this set is equal to $a_1 = 4$.
In the fifth test case, it can be shown that there is no such non-empty set of messages, the reading time of which does not exceed $l$.
Output
一个新消息应用程序计划更新，目的是优化显示给用户的消息集合。总共有n条消息，每条消息由两个整数a_i和b_i表征。阅读消息集合（p_1, p_2, ..., p_k）的时间由以下公式计算：
\[\Large \sum_{i=1}^{k} a_{p_i} + \sum_{i=1}^{k - 1} |b_{p_i} - b_{p_{i+1}}|\]
注意，如果消息集合只包含一个消息p_1，则阅读时间为a_{p_1}。阅读空消息集合的时间认为是0。用户可以确定他愿意在消息应用中花费的时间l。应用必须告诉用户，阅读时间不超过l的最大可能的消息集合大小。注意，消息集合的最大大小可以是0。
输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 5 * 10^4），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数n和l（1 ≤ n ≤ 2000，1 ≤ l ≤ 10^9），分别表示消息的数量和用户愿意在消息应用中花费的时间。
- 接下来的n行，每行包含两个整数a_i和b_i（1 ≤ a_i, b_i ≤ 10^9），表示每条消息的特征。
- 保证所有测试用例的n^2之和不超过4 * 10^6。
输出：
- 对于每个测试用例，输出一个整数，表示阅读时间不超过l的最大可能的消息集合大小。
示例输入输出：
输入：
```
5
5 8
4 3
1 5
2 4
4 3
2 3
1 6
4 10
3 12
4 8
2 1
2 12
5 26
24 7
8 28
30 22
3 8
17 17
5 14
15 3
1000000000 998244353
179 239
228 1337
993 1007
```
输出：
```
3
1
2
1
0
```题目大意： 一个新消息应用程序计划更新，目的是优化显示给用户的消息集合。总共有n条消息，每条消息由两个整数a_i和b_i表征。阅读消息集合（p_1, p_2, ..., p_k）的时间由以下公式计算： \[\Large \sum_{i=1}^{k} a_{p_i} + \sum_{i=1}^{k - 1} |b_{p_i} - b_{p_{i+1}}|\] 注意，如果消息集合只包含一个消息p_1，则阅读时间为a_{p_1}。阅读空消息集合的时间认为是0。用户可以确定他愿意在消息应用中花费的时间l。应用必须告诉用户，阅读时间不超过l的最大可能的消息集合大小。注意，消息集合的最大大小可以是0。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 5 * 10^4），表示测试用例的数量。 - 每个测试用例的第一行包含两个整数n和l（1 ≤ n ≤ 2000，1 ≤ l ≤ 10^9），分别表示消息的数量和用户愿意在消息应用中花费的时间。 - 接下来的n行，每行包含两个整数a_i和b_i（1 ≤ a_i, b_i ≤ 10^9），表示每条消息的特征。 - 保证所有测试用例的n^2之和不超过4 * 10^6。 输出： - 对于每个测试用例，输出一个整数，表示阅读时间不超过l的最大可能的消息集合大小。 示例输入输出： 输入： ``` 5 5 8 4 3 1 5 2 4 4 3 2 3 1 6 4 10 3 12 4 8 2 1 2 12 5 26 24 7 8 28 30 22 3 8 17 17 5 14 15 3 1000000000 998244353 179 239 228 1337 993 1007 ``` 输出： ``` 3 1 2 1 0 ```