{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePutata正在为国际计算机协会(ICPC)举办的RPG Pro League(RPL)做准备。在这个RPG游戏中,玩家可以同时装备$$$n$$$件物品。每件物品可以为玩家提供一定数量的力量点数。游戏中有一个魔法增益,可以升级每件物品,使其可以提供一定数量的额外力量点数。\u003c/p\u003e\u003cp\u003e然而,增益是有限制的,最多只能提升$$$k$$$点力量。具体来说,假设玩家最初没有穿戴任何物品,然后会逐一穿戴所有$$$n$$$件物品。游戏服务器将逐一扫描所有这些$$$n$$$件物品,根据玩家穿戴它们的排列顺序。当服务器扫描到第$$$i$$$件物品时,该物品可以提供$$$p_i$$$点力量,设$$$sum\u003d\\sum_{1\\leq j\u0026lt;i}p_j$$$表示之前总共扫描到的力量点数:\u003c/p\u003e\u003cul\u003e \u003cli\u003e 如果$$$sum+p_i\\leq k$$$,则整件物品将被升级。增益将提供$$$w_{i,p_i}$$$点额外力量。 \u003c/li\u003e\u003cli\u003e 如果$$$sum\\geq k$$$,则该物品不会被升级。增益将不提供任何额外力量。 \u003c/li\u003e\u003cli\u003e 否则,只有部分物品将被升级。增益将提供$$$w_{i,k-sum}$$$点额外力量。 \u003c/li\u003e\u003c/ul\u003e\u003cp\u003ePutata很聪明,他很快意识到可以调整穿戴这$$$n$$$件物品的排列顺序来获得更多额外力量点数!不幸的是,Putata不知道最佳排列顺序,请编写一个程序来帮助他。\u003c/p\u003e\u003cp\u003e游戏服务器执行的魔法增益行为是一个bug。游戏代码能够正常工作完全归功于bug,因此可能$$$w_{i,a}\u0026gt;w_{i,b}$$$的地方$$$a\u0026lt;b$$$。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含两个整数$$$n$$$和$$$k$$$($$$1 \\leq n \\leq 3\\,000$$$,$$$0\\leq k\\leq 3\\,000$$$),表示物品数量和限制$$$k$$$。\u003c/p\u003e\u003cp\u003e接下来的$$$n$$$行中,每行以一个整数$$$p_i$$$($$$1\\leq p_i\\leq 10$$$)开头,表示第$$$i$$$件物品的基础力量,后跟$$$p_i$$$个整数$$$w_{i,1},w_{i,2},\\ldots,w_{i,p_i}$$$($$$1\\leq w_{i,j}\\leq 10^5$$$)。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一行一个整数,表示可以达到的最大总额外力量点数。基础力量不包括在答案中。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 5\n2 1 3\n2 1 1\n2 3 1\n2 1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}