{"trustable":false,"sections":[{"title":"题目大意","value":{"format":"HTML","content":"某周某公司要完成m个项目。为此,公司最多可以从失业机构雇用n人,为期一周。每个外部员工都将花费公司工资欧元,除非他/她所参与的项目没有及时完成。在这种情况下,无需付款。\n\n对于每个项目,公司从经验中知道该项目将在一周内完成的概率,作为参与该项目的员工人数的函数。这些概率以百分比p ij给出,其中i(1 ≤ i ≤ m)是项目的数量,j是从事该项目的人数。当然,当没有人参与项目i 时,概率p i 0为零。\n\n如果项目i确实在一周内完成,公司获得奖励(i)欧元;如果未能及时准备就绪,该公司已支付的罚款处罚(我)欧元。\n\n当然,公司希望通过找到最佳外部员工人数以及如何将他们分配到项目中来最大化其在周末的总预期利润1。最佳员工人数是实现最大预期利润所需的总人数。您在这方面的任务是计算外部员工的最佳数量。请记住,最多有n人可用。此外:如果一个人受雇,他/她只从事一个项目。\n\n1设p (0 \u003c p \u003c 1) 是工作按时完成的概率,E 1是这种情况下的利润。此外,让E 2为(负)利润,以防工作没有及时完成。那么这个特定工作的预期利润是p ⋅ E 1 + (1 − p )⋅ E 2。"}},{"title":"输入格式","value":{"format":"HTML","content":"输入文件的第一行包含一个数字:要遵循的测试用例的数量。每个测试用例具有以下格式:\n\n一行有一个整数m,其中 1 ≤ m ≤ 100:项目数。\n一行包含一个整数n,其中 0 ≤ n ≤ 100:可用员工的最大数量。\n一行 0 ≤工资≤ 1,000 的整数工资:一名员工的工资。请记住,工资以欧元计。\nm行,每行对应一个项目i,包含n 个整数p i 1 , p i 2 , ..., p in(百分比,0 ≤ p i 1 , p i 2 , ..., p in ≤ 100),依次为由对应于项目i的奖励和惩罚的两个整数。所有值都由单个空格分隔。这两种奖励和惩罚 以欧元为单位,介于 0 和 100,000 之间(包括边界)。"}},{"title":"输出格式","value":{"format":"HTML","content":"对于输入文件中的每个测试用例,输出应包含两行。\n\n第一行包含以欧分为单位的最大预期利润。\n第二行包含为实现此最大预期利润而必须雇用的外部员工总数。如果最大的预期利润可以通过不同(总)数量的员工来实现,那么这些不同的数字必须按递增顺序给出。数字必须用单个空格分隔。"}},{"title":"样例输入","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e3\n1\n4\n200\n90 100 100 100 2000 0\n2\n2\n100\n80 80 2100 500\n0 100 1700 500\n3\n4\n100\n100 80 80 70 1000 100\n100 90 80 90 500 50\n100 70 60 50 700 100\u003c/pre\u003e"}},{"title":"样例输出","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e162000\n1\n100000\n1 2\n190000\n3\u003c/pre\u003e"}}]}