题目描述

Perhaps one of the hardest problems of any ACM ICPC contest is to create a problemset with a reasonable number of easy problems. On Not Easy European Regional Contest this problem is solved as follows.

There are $n$ jury members (judges). They are numbered from $1$ to $n$ . Judge number $i$ had prepared $p_{i}$ easy problems before the jury meeting. Each of these problems has a hardness between $0$ and $49$ (the higher the harder). Each judge also knows a very large (say infinite) number of hard problems (their hardness is $50$) . Judges need to select $k$ problems to be used on the contest during this meeting.

They start to propose problems in the ascending order of judges numbers. The first judge takes the first problem from his list of remaining easy problems (or a hard problem, if he has already proposed all his easy problems) and proposes it. The proposed problem is selected for the contest if its hardness is greater than or equal to the total hardness of the problems selected so far, otherwise it is considered too easy. Then the second judge does the same etc. ; after the n-th judge, the first one proposes his next problem, and so on. This procedure is stopped immediately when $k$ problems are selected.

If all judges have proposed all their easy problems, but they still have selected less than $k$ problems, then they take some hard problems to complete the problemset regardless of the total hardness.

Your task is to calculate the total hardness of the problemset created by the judges.

输入格式

The first line of the input file contains the number of judges $n (2 \le n \le 10)$ and the number of problems $k (8 \le k \le 14)$ . The i-th of the following $n$ lines contains the description of the problems prepared by the i-th judge. It starts with $p_{i} (1 \le p_{i} \le 10)$ followed by $p_{i}$ non negative integers between $0$ and $49$ -- the hardnesses of the problems prepared by the i-th judge in the order they will be proposed.

输出格式

Output the only integer -- the total hardness of the selected problems.

3 8
5 0 3 12 1 10
4 1 1 23 20
4 1 5 17 49

94

3 10
2 1 3
1 1
2 2 5

354

提示

Time limit: 1 s, Memory limit: 256 MB.