MAC 中的信使

时间限制：3s
空间限制：256MB

题目描述

有 $n$ 条消息，第 $i$ 条消息由两个整数 $a_i$ 和 $b_i$ 描述。

若按顺序阅读编号为 $p_1,p_2,\ldots,p_k$ 的若干条消息，其中所有编号两两不同，则所需时间为

$$\sum_{i=1}^{k} a_{p_i}+\sum_{i=1}^{k-1}|b_{p_i}-b_{p_{i+1}}|$$

只阅读一条消息时，所需时间为该消息的 $a_i$；不阅读任何消息时，所需时间为 $0$。

给定时间上限 $l$，求在总阅读时间不超过 $l$ 的前提下，最多可以阅读多少条消息。答案可以为 $0$。

输入格式

第一行包含一个整数 $t$，表示测试用例数量。

对于每个测试用例：

• 第一行包含两个整数 $n,l$，分别表示消息数量和时间上限。
• 接下来 $n$ 行中，第 $i$ 行包含两个整数 $a_i,b_i$，表示第 $i$ 条消息的两个参数。

输出格式

对于每个测试用例，输出一行一个整数，表示最多可以阅读的消息数量。

样例输入 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

数据范围

• 对于所有数据，满足 $1 \le t \le 5 \cdot 10^4$。
• 对于所有数据，满足 $1 \le n \le 2000$。
• 对于所有数据，满足 $1 \le l \le 10^9$。
• 对于所有数据，满足 $1 \le a_i,b_i \le 10^9$。
• 所有测试组共同满足 $\sum n^2 \le 4 \cdot 10^6$。

子任务编号	分值	特殊限制
1	10	$t \le 12$，且每个测试用例均满足 $n \le 14$
2	20	对于每个测试用例，所有 $b_i$ 相等
3	30	$t \le 20$，且每个测试用例均满足 $n \le 60$
4	40	无特殊限制