CF1935C.Messenger in MAC

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.

在面向“大师援助中心”学生的新型即时通讯软件 Keftemerum 中，计划进行一次更新，开发者希望优化向用户展示的消息集合。一共有 $n$ 条消息。每条消息由两个整数 $a_i$ 和 $b_i$ 描述。阅读编号为 $p_1, p_2, \ldots, p_k$（其中 $1 \le p_i \le n$，且所有 $p_i$ 互不相同）的消息集合所需的时间，由如下公式计算：

$$\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$。

这款广受欢迎的即时通讯软件的开发者未能实现此功能，因此他们请你来解决该问题。

Each 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$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 5 \cdot 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $l$（$1 \leq n \leq 2000$，$1 \leq l \leq 10^9$），分别表示消息数量以及用户愿意在该即时通讯软件中花费的时间。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^9$），表示第 $i$ 条消息的特征。

保证所有测试用例中 $n^2$ 的总和不超过 $4 \cdot 10^6$。

For 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$.

对于每个测试用例，输出一个整数——满足阅读时间不超过 $l$ 的消息集合的最大可能大小。

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$.

在第一个测试用例中，你可以选择一组三条消息，其编号分别为 $p_1 = 3$、$p_2 = 2$ 和 $p_3 = 5$。阅读该组消息所花费的时间为 $a_3 + a_2 + a_5 + |b_3 - b_2| + |b_2 - b_5| = 2 + 1 + 2 + |4 - 5| + |5 - 3| = 8$。

在第二个测试用例中，你可以选择一组仅含一条消息，其编号为 $p_1 = 1$。阅读该组消息所花费的时间为 $a_1 = 4$。

在第五个测试用例中，可以证明：不存在满足条件的非空消息集合，使得其阅读时间不超过 $l$。