SHUB1307 - Gupta ji Birthday !!

It's the 13th of July and it's Shubham Gupta's Birthday. Shubham loves to solve DP problem. Anuj (Shubham's friend) want to wish him uniquely. So he decorate their hostel room number 235 where the floor is divided into N × M square tiles, forming a grid with N rows and M columns.

Each square in the grid contains a number of vodka shots that Shubham has to drink if he steps on a particular tile. Shubham enters the room on (1, 1) and has to makes his way to the exit gate on (N, M), drinking the vodka on the way. From the current cell, he can move only to the adjacent cell in East, South or South-East direction i.e. from (i, j) to either (i, j+1) , (i+1, j) or (i+1, j+1).

However, his capacity for the vodka is limited. If he drink more than K shots, he will be out of control! Help him find a way to drink as any many shots as he can, without going out of control.

Input

The first line contains T. T test cases follow.
First line of each test case contains 3 space-separated integers, N, M, K.
Each of the following N lines contain M space-separated integers, describing the grid.

Output

Print the maximum number of vodka shots that he can drink without going out of control or "-1" (without the quotes) if it can not be done i.e. if there does not exist such a path. Print the answer to each test case on a new line. .

Constraints:

1 ≤ T ≤ 10
1 ≤ N, M ≤ 100
1 ≤ K ≤ 500
1 ≤ Values in the Grid ≤ 50

Example

Input:
2
3 3 7
2 3 1
6 1 9
8 2 3
3 4 9
2 3 4 1
6 5 5 3
5 2 3 4

Output:
6
-1

Explanation

In the first test case, he can move on squares (1, 1) , (2, 2) and (3, 3) to complete his journey with 6 shots. In the second test case, every possible path leads to the drinks of more than 9 shots.


Added by:APC
Date:2016-07-12
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2021-06-03 23:42:30
@akshayvenkat same problem br0
2019-01-20 16:03:05
bfs also works since the search space is small
2018-07-02 20:36:33
my first 3D dp and also my 200th :)
2018-04-11 13:05:26
Gupta ji likes his present!!!! :P
2016-07-16 01:43:42 nikoo28
@APC: Constantly getting TLE. Please check my submission id 17292056.

Last edit: 2016-07-16 18:57:19
2016-07-15 09:52:12 Siddharth Singh
I Had To Do Quite Lot Of Research To Reach To a Solution.
Anyways , Feeling Happy.
Best Solution <3
0.08 & 0.09 :P
2016-07-15 07:00:59 Sushovan Sen
Judge will not stop at first failure. It will run up to last test case anyway.

Last edit: 2016-07-15 07:01:51
2016-07-13 18:18:31
getting wrong answer on the 8th test case.. someone help?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.