FISHER - Fishmonger

A FishmongerA fishmonger wants to bring his goods from the port to the market. On his route he has to traverse an area with many tiny city states. Of course he has to pay a toll at each border.

Because he is a good business man, he wants to choose the route in such a way that he has to pay as little money for tolls as possible. On the other hand, he has to be at the market within a certain time, otherwise his fish start to smell.

Input

The first line contains the number of states n and available time t. The first state is the port, the last state is the market. After this line there are n lines with n numbers each, specifying for each state the travel time to the i-th state. This table is terminated with an empty line. The table of the tolls follows in the same format.

n is at least 3 and at most 50. The time available is less than 1000. All numbers are integers.

There are many test cases separated by an empty line. Input terminates with number of states and time equal 0 0.

Output

For each test case your program should print on one line the total amount of tolls followed by the actual travelling time.

Example

Sample input:
4 7
0 5 2 3
5 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

0 0

Sample output:
6 6

This corresponds to the following situation, the connections are labeled with (time, toll):


Added by:MichaƂ Czuczman
Date:2004-07-07
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Swiss Olympiad in Informatics 2004

hide comments
2017-07-15 14:05:14
AC in 1 go !! *)
2017-04-16 12:05:48
:) \n
2017-03-07 16:55:03
The problem statement should specify that travel time is always positive; it makes sense, but if some states had teleporters, my solution - and probably many others - wouldn't work.

Also, an example with min time != min cost would have been nice, so it was clear which was which; especially since the input gives <time, cost> while your output is <cost, time>.
2016-10-20 20:43:43
First matrix is tolls matrix second matrix is time matrix !
2016-08-18 17:26:31 Ahmed Hussein
50 * 50 * 1000 iterative will pass
2016-07-01 10:16:27 Shivang Badola
Take care that you read TIME first then TOLLS..cost me many WA.
2016-06-23 14:45:27 PARTH SHARMA
dp in time :))
2016-05-16 07:00:31
TLE with recursion(DFS)...solved with DP(knapsack)...
but still cant figure the approach with dijkstra :(
got it......thanx narutorocks



Last edit: 2016-06-15 09:24:32
2016-01-26 07:15:53 epsilon
can someone please explain the input format

Last edit: 2016-01-26 07:16:14
2015-12-17 15:48:38 sudhanshu monga
woah ! what a knapsack ! :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.