Description

众所周知，$LW$是1816的风云人物，然而寒假集训期间，LW实在卷不动了，于是为了逃离各位卷王们，又不集训了，乘着寒假时分再次南下干流水线了。

$LW$所在的流水线是专门做切割棍子的，$LW$所要做的就是把流水线上过来的木头不太好的部分切割下来丢进垃圾桶，把剩下好的部分接起来继续顺着流水线往下。

由于在$LW$前面的工人(小T)是个新来的，所以经过小T加工过的一根木头，往往是某一段加工还行，某一段差点，某一段就特别拉跨。(不要问是怎么加工出来的，问就是小T YYDS)

为了简化情况，对于小T加工出来的一根木棍，$LW$会根据品质的不同将其按从左到右的顺序分成连续的 $n$ 段，对于每一段$LW$会给出这一段的木头品质$a_i$，并给出这一段木头的长度 $l_i$。

评定效果如图：

每种颜色代表分出来的一段，段与段长度不一定相等，同样品质也不一定相等

$LW$只能将选一些切割点 (可能没有，但要选的话不能选在一段完整段之内，即切割点只能选在两个不同的段之间) ，并将切完之后分开的几个部分任选一些 (同样可以没有) 丢弃，然后把剩下的部分重新接成一个新的木棍。这根新木棍的品质即为剩下的部分的品质之和。

对于这个新的木棍，$LW$希望它的长度不能超过$D$，且品质最大。由于$LW$很懒，秉着能少做一点就少做一点的原则下，即在在保证品质最大的情况下，要求你切割的次数最少 。

Input Format

题目包含多组样例，在第一行输入一个$t$ $(1≤t≤5)$，表示样例个数。

对于每组样例，在第一行输入两个整数$n$, $D$ $(1≤n, D≤1000)$，$n$表示这根木棍分出来的段数，$D$表示木棍的最长长度限制。

接下来$n$行，每行包含两个整数$a_i$, $l_i$ $(1≤a_i≤1000, 1≤l_i≤1000)$，表示按从左到右顺序的每一段的品质$a_i$和长度$l_i$。

Output Format

对于每个样例在一行输出两个整数。分别表示切割完后新的木棍品质的最大值和切割所需的最小次数。 (题目保证新木棍至少有一段)

2
5 3
1 1
1 1
1 1
1 1
1 1
3 4
2 2
2 4
2 2

3 1
4 2

Hint

对于第一个样例

棍子原本的长度为5，但是限制必须小于3，所以我们至少得切下两个部分，显然由于每个部分品质都一样，所以我们只要切一刀就可以完成了，然后把左边的的两个段的部分丢掉就好了。

对于第二个样例

我们要品质最大，只能用两刀把中间那段切掉，用剩下的两个品质为2的木棍组成品质为4的新木棍。