题目描述
故事发生在很久很久以前。一天，曹操向他的军队下了一道特殊的命令，叫做“鸡肋”。没人明白他的意思，所有人都很慌张，而曹操却为自己这个有趣的主意感到得意。
曹操最聪明的谋士之一——杨修看懂了这道命令，并把它讲给了全军。曹操对他的聪明很生气，想惩罚杨修。他看着鸡肋，终于想出了一个新点子来惩罚杨修：
他告诉杨修，作为加密这道命令的奖赏，他可以从桌上拿走尽可能多的金条，但只能用一根棍子作为容器。
形式上，容器是一根长度为 $L$ 的线段，金条也是线段。桌上有许多长度 $a_i$、价值 $v_i$ 各不相同的金条。杨修需要把这些金条放到容器上，任何两根金条不能重叠。幸运的是，杨修想出了一个好主意：在容器的两侧，他可以让金条的一部分露在容器外，只要每根金条的重心仍在容器内即可。这能帮他拿到更多有价值的金条。
请问杨修最多能拿到总价值为多少的金条？
输入格式
第一行是一个整数 $T(1\le T \le 100)$，表示测试数据组数。
每组测试数据第一行是两个整数 $N(1\le N \le 1000)$ 和 $L(1\le L\le 2000)$，表示金条数量和容器长度。
接下来 $N$ 行，每行两个整数 $a_i(1\le a_i \le 2000)$ 和 $v_i(1\le v_i \le10^9)$，表示第 $i$ 根金条的长度和价值。
输出格式
对每组测试数据，输出一行：
Case #x: y其中 $x$ 是测试数据编号（从 1 开始），$y$ 是杨修能拿到的最大总价值。
样例
输入：
4
3 7
4 1
2 1
8 1
3 7
4 2
2 1
8 4
3 5
4 1
2 2
8 9
1 1
10 3输出：
Case #1: 2
Case #2: 6
Case #3: 11
Case #4: 3提示：第三组数据中，假设容器在 $x$ 轴上从 $0$ 到 $5$，杨修可以把第二根金条的重心放在 $0$，第三根金条的重心放在 $5$，这样两根都不会掉下来，总价值 $2+9=11$。第四组数据中，杨修只需把唯一一根金条的重心放在 $[0,1]$ 的任意位置即可，价值为 $3$。
数据范围与子任务
\begin{array}{|c|c|c|} \hline \textbf{子任务} & \textbf{分值} & \textbf{数据范围} \\ \hline 1 & 20 & N\le 20,L\le 50 \\ \hline 2 & 30 & N\le 100,L\le 200 \\ \hline 3 & 50 & N\le 1000,L\le 2000 \\ \hline \end{array}
- 对于 100% 的数据：$1\le T \le 100,1\le N \le 1000,1\le L \le 2000,1\le a_i \le 2000,1\le v_i\le 10^9$。