Jack is a wise and miser man. Always tries to save his money.
One day, he wants to go from city A to city B. Between A and B, there are N number of cities(including B and excluding A) and in each city there are M buses numbered from 1 to M. And the fare of each bus is different. Means for all N*M busses, fare (K) may be different or same. Now Jack has to go from city A to city B following these conditions:
You are to help Jack to go from A to B by spending the minimum amount of money.
N, M, K <= 100.
Line 1: N M
Line 2-: NxM Grid
Each row lists the fares the M busses to go form the current city to the next city.
Single Line containing the minimum amount of fare that Jack has to give.
Input: 5 5 1 3 1 2 6 10 2 5 4 15 10 9 6 7 1 2 7 1 5 3 8 2 6 1 9 Output: 10
1 -> 4 -> 1 -> 3 -> 1: 10