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 buses, 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 <= 100.

Input

Line 1: N M

Line 2: N×M Grid

Each row lists the fares the M busses to go form the current city to the next city.

Output

Single Line containing the minimum amount of fare that Jack has to give.

Example

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

Explanation

1 → 4 → 1 → 3 → 1: 10


hide comments
ameyanator: 2018-01-23 19:18:51

Simple table filling question :')

surajmall: 2017-10-22 22:33:07

dp for beginners for start dp :)

prince kumar: 2017-04-04 21:29:13

same as BYTESM2 but it hasn't got c++4.3.2 option. Submitted same code (with option c++(gcc6.3) )and got WA in BYTESM2 but AC in MISERMAN (with option c++(gcc4.3.2) ) . Can't figure out difference in the option selected as both are c++!!

rishabh_nitw: 2017-03-23 10:28:54

BottomUp DP Easiest :P Read Multistage Graph

vladimira: 2017-03-16 05:32:59

Easiest dp.

nilabja16180: 2017-03-06 18:37:01

DP is great!
AC in one GO! 0.00 sec!

Last edit: 2017-03-06 18:38:08
shahzada: 2017-03-06 15:26:37

Easiest DP problem. AC- 0.00s

Last edit: 2017-03-06 15:26:59
vineetpratik: 2017-02-27 15:39:21

Same as philosopher's stone

scorpion_ajay: 2017-02-25 19:41:10

try philosphors stone before this one..... though both are same;
AC in a go ;)

vengatesh15: 2017-01-18 16:16:03

Simple one..


Added by:The quick brown fox jumps over the lazy dog
Date:2010-10-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC VB.NET
Resource:Udit Agarwal