曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5738: 取数游戏

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：53 Solved：17
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

有N行数字，现在要从所有的数字中选择M个。保证每一行的数都是从小到大排序的。同一行内的数字只能从左往右取。例如：如果要取第一行的第二个就必须先取走第一行的第一个。现在要使得选出的M个数字和最小。

Input

第一行两个数N，M。
接下来有N行，每行先有一个数x[i]表示这一行的数字个数，接下来有x[i]个数，保证从小到大排序。

Output

一个数字表示最小的数字之和。

Sample Input Copy 

4 3
2 7 8
1 9
1 10
1 11

Sample Output Copy 

24

HINT

样例解释：选择了以下三个数：第一行第一个数7，第一行第二个数8，第二行第一个数9。