Kevin的宝石
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\sf I\ feel\ something\ so\ right

\sf Doing\ the\ wrong\ thing

               —— Counting\ Stars,\ \text{OneRepublic}
氧气少年将 n 枚宝石排成一排，有的是普通宝石，有的是魔法宝石。第 i 颗普通宝石的价值为 v_i，第 i 颗魔法宝石的价格为 w_i。

氧气少年每次可以进行下面的操作：
  •  选择任意两颗相邻的魔法宝石（中间没有未消去的魔法宝石）并将它们买下，然后将这两颗魔法宝石以及它们之间的普通宝石全部消去，并获得它们之间的普通宝石的全部价值。

编号为 i 的魔法宝石和编号为 j 的魔法宝石相邻是指：编号为 i 的魔法宝石和编号为 j 的魔法宝石之间没有任何没被消去的魔法宝石。
将编号为 i 的魔法宝石和编号为 j 的魔法宝石买下是指：花费 w_i+w_j 的钱数将它们买下。
将宝石消去后，其它宝石的编号不受影响。

阅读样例解释有助于理解上述过程。

现在，氧气少年拥有的钱数为 k。请求出他能获得的最大价值。

输入描述:

第一行包含一个整数 T(1\leq T \leq 1000)，表示测试用例的组数。

对于每组测试用例：

第一行包含两个整数 n(1\leq n\leq 5000), k(0\leq k\leq 5000)，表示宝石的数量和氧气少年拥有的钱数。

接下来 n 行，每行包含两个整数 x(1\leq x\leq 2),y(1\leq y\leq 10^9)。
  •  如果 x=1，那么此宝石为普通宝石。假设当前普通宝石为第 i 颗普通宝石，那么称它为编号为 i 的普通宝石，它的价值 v_i = y；
  •  如果 x=2，那么此宝石为魔法宝石。假设当前魔法宝石为第 i 颗魔法宝石，那么称它为编号为 i 的魔法宝石，它的价格 w_i = y。

保证对于所有的测试用例，n 的总和不超过 5000。

输出描述:

对于每组测试用例：
仅输出一行，包含一个整数，表示答案。
示例1

输入

复制 
3
6 10
2 5
1 10
1 20
2 5
1 40
2 5
3 5
1 10
2 1
2 1
12 50
1 100
2 5
1 50
1 10
2 15
1 50
1 30
1 10
2 10
1 70
1 5
2 20

输出

复制 
40
0
225

说明

对于第一组样例数据：
可以买下编号为 2 的魔法宝石和编号为 3 的魔法宝石，并将这两颗魔法宝石及其中间的 3 号普通宝石全部消去，获得的价值为 40。

对于第三组样例数据：
第一步：买下编号为 2 的魔法宝石和编号为 3 的魔法宝石，并将这两颗魔法宝石及其中间的 4,5,6 号普通宝石全部消去，获得的价值为 50+30+10=90。第二步：买下编号为 1 的魔法宝石和编号为 4 的魔法宝石，并将这两颗魔法宝石及其中间的 2,3,7,8 号普通宝石全部消去，获得的价值为 50+10+70+5=135。总价值为 90+135=225。