I couldn't come up with a solution for this.can anyone help me out?

Problem Statement:

Lord Zampa loves to collect newspapers, he has this huge store in his palace. He has kept all the newspapers in n slots and within each slot the newspapers are properly arranged in a row so that only the newspapers on the extreme ends are accessible to read. Once a newspaper is taken out it can never be kept again..
You will be surprised to know that Lord selects m newspapers to read at a time and chooses them according to their weight, funny isn't. Also, he never read a newspaper again. As you can guess Lord is not smart enough, help him by finding the maximum weight of the m newspapers he has to read currently.

Input
The first line of input data contains two integers n and m. The next n lines contain the weights of the newspapers on the slots: the first number on each line gives the number of newspapers on this slot, followed by the weight of the newspapers, in the order in which they appear on the slot where the first number is the weight of leftmost newspaper and the last one is the weight of the rightmost newspaper. The total number of newspapers is guaranteed to be at least m.

CONSTRAINTS
1<=n<=100
1<=m<=10000

Output

Output the maximum weight of newspapers for the Lord.

SAMPLE INPUT 1

2 3
3 3 7 2
3 4 1 5

SAMPLE OUTPUT 1
15
Explanation:
In the first case there are two shelves with three newspapers each. To maximize the total weight of the newspapers, take two newspapers from the left side of the first slot and one from the right side of the second slot. In the second case there is only one slot, two newspapers chosen from the left side and one from the right side.