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
ayushsatyam146: 2020-08-03 18:59:40

mujhe ye ac in 1 go wale comments dekh ke maut aa rahi h par ho gaya kisi tarah

tgcgowtham: 2020-05-30 19:45:41

Poor Test Cases - RIP for AC

ks1999: 2020-04-29 04:03:38

solve it with 2d dp matrix, i think it is easier to implement and also it's more efficient. This is classical problem of min cost in matrix, must for beginners.

manish_thakur: 2020-03-31 19:50:16

new to dp, was about to give up and look for solution, but thought of giving it a try and after half an hour of trying got an ac, don't get demotivated by looking at those "AC in one go" comments, keep going!

apoorva222g: 2020-01-26 11:05:06

easy dp problem of 2d array

dhj: 2020-01-21 14:36:42

getting back to spoj after 3 years and getting an AC in a go is an amazing feeling

harry_shit: 2019-11-14 20:45:55

ac in one go after ages, simple dp :)

zsumon: 2019-07-30 03:21:10

weak dataset!

scolar_fuad: 2019-07-07 15:59:42

Simple dp used top up approach with memorization

duke_knight: 2019-06-24 08:25:16

AC in 1 go!!


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