SP7588 MISERMAN - Wise And Miser

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: 1. At every city, he has to change the bus. 2. And he can switch to only those buses which have number either equal or 1 less or 1 greater to the previous. You are to help Jack to go from A to B by spending the minimum amount of money. N, M, K

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.