Sameer has scored very less marks in midsem exams.
To prepare for endsem exams he has to study N different subjects.
Meet being a good friend of Sameer has decided to help him for endsem exams.
Meet and Sameer went to the college library to borrow some books for exam.
Luckily there are exactly N stacks of book .
Each stack for a subject. Each book has a page value, the total number of pages in it.
Meet has to take exactly B books. If he takes a book from a stack, he must also take all of the books above it in that stack as well.
Meet can choose to take no book from a stack.
Input
The first line of the input gives the number of test cases, t. Each test case begins with a line containing the three integers N, K and B. Then, N lines follow. The i-th line contains K integers, describing the number of pages of each stack of book from top to bottom.
Output
For each test case, output one line , the maximum total sum of page value that Meet could pick.
Constraints
1 ≤ T ≤ 100.
1 ≤ K ≤ 30.
1 ≤ P ≤ N * K.
The page value is between 1 and 100, inclusive.
In the first test case You needs to pick 5 books:
You can pick the top 3 books from the first stack (10 + 10 + 100 = 120).You can pick the top 2 books from the second stack (80 + 50 = 130) .In total, the sum of page value is 250.
In In the second test case , you needs to pick 3 books:
You can pick the top 2 books from the first stack (80 + 80 = 160).You can pick no books from the second stack.You can pick the top books from the third stack (20).In total, the sum of beauty values is 180.
