FPOLICE  Fool the Police
Dhamaka Singh (a crook) has just robbed a bank and would like to get out of the country as soon as possible. But there is a slight problem, the police! On his way out of the country he has to pass through some police stations. Each police station has a certain risk (for Dhamaka Singh) associated with it. He wants to get to the airport within a certain time T or else he'll miss his flight. He also wants to take a path that minimizes the total risk associated with it. Help Dhamaka Singh get out of the country.
Input
The first line of the input contains an integer t, the number of test cases. t test cases follow.
The first line of each test case contains 2 integers N (3 <= N <= 100) and T (1 <= T <= 250), denoting the number of police stations and the total time he has to reach the airport, respectively.
Dhamaka Singh has to start from the first police station and reach the N^{th} one (the airport is just after the N^{th} police station). You can consider the time taken between the N^{th} police station and the airport to be negligible.
Next there are N lines with N numbers in each line, separated by single spaces. All numbers are separated by a single space. The j^{th} integer in the i^{th} line represents the time taken to reach the j^{th} police station from the i^{th} police station.
Next there are another N lines with N numbers in each line. All numbers are separated by a single space. The j^{th} integer in the i^{th} line represents the risk involved in travelling to the j^{th} police station from the i^{th} police station.
Output
For each test case output one line containing 2 integers separated by a single space.
The first integer denotes the minimum total risk to reach the airport. The second integer denotes the minimum time required to reach the airport at the minimum total risk.
If it is impossible to reach the airport within time T (inclusive), just print "1" (quotes for clarity).
Example
Input: 1 4 10 0 6 2 3 6 0 2 3 3 1 0 2 3 3 2 0 0 2 2 7 2 0 1 2 2 2 0 5 7 2 5 0 Output: 4 9
hide comments
JP:
20170206 14:08:23
My 100th! :) 

aspro:
20160516 07:01:50
TLE with recursion(DFS)...solved with DP(knapsack)...


:.Mohib.::
20151108 09:20:09
Finally AC :) 

theweblover007:
20151102 18:02:00
Dont know i am getting WA when i get right answer for all the test cases. 

Naman Goyal:
20150519 23:56:00
The problem setters should put all the constraints like limit of risk integer? It becomes easier to select datatypes and other constraints in the code. 

N0VICE:
20150102 10:32:07
AC after many WAs :) 

OTAKU:
20141228 16:40:00
finally recursion helps me ... :) 

AlcatraZ:
20140819 22:11:05
Finding time was little tricky.. Nice question.. AC with DP.. Dijkstra WA 

Cosmos:
20140624 08:28:49
recursion with not so much of DP... 

Himank Agrawal:
20140519 21:04:57
what is max value of t(test cases) ? 
Added by:  Matthew Reeder 
Date:  20061029 
Time limit:  1.411s 
Source limit:  30000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  AlKhawarizm 2006 