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

Input

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.

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
soub5184: 2019-02-16 14:36:22

Submitted in java.AC in one go.

ashimk: 2019-01-07 20:55:56

Recursion + Memoization did it for me :)
An easy one !!
Good for beginners !

amvi: 2018-11-08 11:34:18

no dp only recursion

itssanat: 2018-10-26 22:02:45

AC in one go :):) !!!!

masterchef2209: 2018-10-11 23:42:07

AC in 1 go easy peasy dp

deepak097: 2018-08-11 23:53:22

Same as problem "Philosophers stone" :)

roshan172: 2018-07-25 21:19:45

Simple Bottom up algo can work for this.

thisistia: 2018-06-26 11:49:21

Came here from the Philosopher's Stone problem..do try both. Great start for anyone starting out Dynamic Programming!

vivek_rathi: 2018-03-26 11:50:43

Simple Dp! AC in One Go!!!

richardks3647: 2018-03-03 08:16:22

c++(gcc4.3.2) doesn't work, careful


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