CF1935C Messenger in MAC

在硕士援助中心的学生专用新消息应用 Keftemerum 中，开发者计划进行一次更新，旨在优化展示给用户的消息集合。共有 $n$ 条消息。每条消息由两个整数 $a_i$ 和 $b_i$ 描述。阅读编号为 $p_1, p_2, \ldots, p_k$（$1 \le p_i \le n$，所有 $p_i$ 互不相同）的一组消息所需的时间按如下公式计算： $$ \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 \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$。

对于每个测试用例，输出一个整数——在不超过 $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$。 由 ChatGPT 4.1 翻译