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


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

hide comments
2022-08-24 04:54:34
my dumb ass can't understand this lmao.
edit: nvm its similar to BYTESM2(SPOJ)

Last edit: 2022-08-24 06:38:21
2021-11-21 13:56:13
O(2*M) space dp less gooooo !!!!
2021-01-15 19:34:33
what is difference between this question and philosoper stone . in philosoper stone we have to find maximum value and in this question minimum. can't get this . please help.



Got IT!!!

Last edit: 2021-01-15 19:48:45
2020-11-29 06:41:06
One needs to fill the last row first and then proceed. Simple problem.
2020-11-29 06:40:11
AC in one go!
2020-11-01 02:57:03
nice problems
2020-10-22 03:17:56
I'm new in dp, but i got ac in 1 go. nice problem to practice :)
2020-10-05 21:00:29 Abhishek gupta
weak test cases, without DP with recursion it is accepting.
2020-08-05 23:03:29
Try to maintain a minimum cost for each block in the form of a table, and this can be done simply as we know that if we arrive at this block then what were our previous choices. And the answer is the smallest element in the last row of this table.

Last edit: 2020-08-07 19:47:28
2020-08-05 08:57:32
Recursion + Memo ♥
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.