问题2615--【区赛】【鄞州2016】期末考试

2615: 【区赛】【鄞州2016】期末考试

时间限制: 1 Sec  内存限制: 128 MB
提交: 3  解决: 2
[提交] [状态] [讨论版] [命题人:]

题目描述

小东马上就要期末考试,而他是个不折不扣的学渣,平时不学全靠期末复习临时抱佛脚。他总共有n 门科目要考试而他还有m 小时的复习时间,每门科目投入不同的时间能获得不同分数(每科分数小于等于100 )。请问小东怎样安排复习时间才能使期末总分最高?

输入

第一行两个整数n,m

接下来n 行,每行第一个数k ,表示这门课能获得的不同分数的档数,接下来2k 个数表示投入的时间和获得的分数。

输出

一个整数表示最高的总分

样例输入 Copy

3 60
2 10 60 50 100
3 10 50 20 70 30 90
1 40 80

样例输出 Copy

190

提示

样例解释:第一门课投之10h 得到 60 分,第二门投入10h得到50分,第三门课投入40h得到80分,总共190分。
注:若在第一门课投入60小时,也只能获得100分,而不是160,同理在第二门课投入超过30 小时也只能获得90 分。

40% n <=15, k <=2

60% n <=100, m <=100 ,k <=3

100% n <= 1000 , m <=1000 , k <=5

来源/分类