{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\n故事发生在很久很久以前。一天,曹操给他的军队下达了一个特殊的命令,叫做“鸡肋”。没有人理解他的意图,所有人都陷入了恐慌之中。\n然而,曹操自己对他有趣的想法感到非常自豪,并且享受其中。\n\n曹操最聪明的谋士之一,名叫修阳,理解了这个命令。他不仅没有独自保留这个秘密,还告诉了整个军队。曹操对他的聪明才智感到非常生气,并且想要惩罚修阳。但是你怎么能因为一个人聪明而惩罚他呢?通过看着鸡肋,他终于想出了一个惩罚修阳的新主意。\n\n他告诉修阳,作为他加密特殊命令的奖励,他可以从他的桌子上拿走尽可能多的金条。但是他只能使用一根金条作为容器。\n\n正式地说,我们可以将容器金条视为长度为$L$的线段。金条也是线段。有许多不同长度$a_i$和价值$v_i$的金条。\n修阳需要将这些金条放在容器线段上。不允许金条重叠。幸运的是,修阳想出了一个好主意。在容器的两侧,他可以让部分金条超出容器,只要每根金条的重心仍然在容器内部即可。这可以帮助他获得更有价值的金条。\n\n结果,修阳拿了太多的金条,这让曹操更加生气。曹操在回家之前就杀了修阳。所以没有人知道修阳在容器中放了多少金条。\n\n你能帮助解开这个谜团,找出修阳可能拿到的金条的最大价值吗?\n"}},{"title":"输入","value":{"format":"MD","content":"输入的第一行包含一个整数$T$($1\\leq T\\leq 100$),表示测试用例的数量。接下来的$T$行,每行包含两个整数$N$($1\\leq N\\leq 1000$)和$L$($1\\leq L\\leq 2000$),表示金条的数量和容器金条的长度。接下来的$N$行,每行包含两个整数$a_i$($1\\leq a_i\\leq 2000$)和$v_i$($1\\leq v_i\\leq 10^9$),表示第$i$个金条的长度和价值。"}},{"title":"输出","value":{"format":"MD","content":"对于每个测试用例,输出一行,包含`Case #x: y`,其中$x$是测试用例的编号(从$1$开始),$y$是修阳可能拿到的金条的最大价值。"}},{"title":"示例1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003e输入\u003c/th\u003e\n \u003cth\u003e输出\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\n3 7\n4 1\n2 1\n8 1\n\n3 7\n4 2\n2 1\n8 4\n\n3 5\n4 1\n2 2\n8 9\n\n1 1\n10 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 2\nCase #2: 6\nCase #3: 11\nCase #4: 3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"MD","content":"在第三个测试用例中,假设容器在$x$轴上从$0$到$5$。修阳可以将第二个金条的中心放在$0$,将第三个金条的中心放在$5$,这样它们都不会掉下来,他可以获得总价值$2+9\u003d11$。在第四个测试用例中,修阳只需要将唯一的金条的中心放在$[0,1]$的任意位置,他就可以获得价值$3$。"}}]}