← 返回题目列表

Codeforces · 1935/C

C. MAC 中的 Messenger

中文机器翻译题面 查看原题

在为硕士援助中心 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$$$。

用户可以确定他愿意在Messenger上花费的时间$$$l$$$。信使必须告知用户该组消息的最大可能大小,其阅读时间不超过$$$l$$$。请注意,消息集的最大大小可以等于 $$$0$$$。

流行的Messenger的开发人员未能实现此功能,因此他们要求您解决此问题。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$l$$$ ($$$1 \leq n \leq 2000$$$, $$$1 \leq l \leq 10^9$$$) — 消息的数量和用户愿意在Messenger中花费的时间。

接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$) — 第 $$$i$$$ 消息的特征。

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

输出

对于每个测试用例,输出一个整数——一组消息的最大可能大小,其读取时间不超过$$$l$$$。

示例

输入 #1

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

输出 #1

3
1
2
1
0

注意

在第一个测试用例中,您可以获取一组三个消息,其编号为 $$$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$$$的非空消息集。