SHUB1307 - Gupta ji Birthday !!


Its 13th of July and its 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 no. 235 where the floor is divided into N x 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 testcases follow.
First line of each testcase 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 testcase in 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 testcase, he can move on squares (1,1) , (2,2) and (3,3) to complete his journey with 6 Shots. In the second testcase, every possible path leads to the drinks of more than 9 Shots.


hide comments
raj_nitj1234: 2021-06-03 23:42:30

@akshayvenkat same problem br0

smso: 2019-01-20 16:03:05

bfs also works since the search space is small

anirudnits: 2018-07-02 20:36:33

my first 3D dp and also my 200th :)

shubh_nitdgp: 2018-04-11 13:05:26

Gupta ji likes his present!!!! :P

nikoo28: 2016-07-16 01:43:42

@APC: Constantly getting TLE. Please check my submission id 17292056.

Last edit: 2016-07-16 18:57:19
Siddharth Singh: 2016-07-15 09:52:12

I Had To Do Quite Lot Of Research To Reach To a Solution.
Anyways , Feeling Happy.
Best Solution <3
0.08 & 0.09 :P

Sushovan Sen: 2016-07-15 07:00:59

Judge will not stop at first failure. It will run up to last test case anyway.

Last edit: 2016-07-15 07:01:51
akshayvenkat: 2016-07-13 18:18:31

getting wrong answer on the 8th test case.. someone help?


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