N trains are standing on a station, parallel to each other. Each train can be viewed as a row of matrix. Each train has some bogies. Each bogie has some amount of cash inside it. You can only remove bogies from front and end of the train (if you remove the front bogie, you can also remove 2nd bogie from front). You are allowed to remove maximum of M bogies.
Find the maximum cash that you can collect.
INPUT
First line contains the integers N and M, denoting number of trains and maximum number of bogies that can be removed.
First integer of each of the next N lines is P, representing number of bogies in a train. Next P integers represent cash in bogies of train. First integer is cash in first bogie and last integer is cash in last bogie.
It is guaranteed that number of bogies are at least M.
OUTPUT
Output single integer, maximum cash possible.
CONSTRAINTS
1<=N,P, cash in a bogie<=100
1<=M<=104
We can select only 3 numbers, so we can select 4,2 from 2nd row and 3 from 1st row, or we can select 4 from 2nd row and 2,3 from first row. So, max possible sum is 2+3+4=9
