Jinwoo's Moon Trip (Large)

Interview

Time limit1sMemory limit256 MB

Summary
Find the cheapest path from any cell in the top row to any cell in the bottom row of an N x M grid, where no two consecutive moves may use the same direction.
Level

Medium7 of 10

Topics
Dynamic programming, Matrix, Implementation, Greedy
Solved
No attempts yet

Problem

Jinwoo, whose dream was spaceflight, worked hard at the restaurant 'Fresh Every Day' and saved up all the money he needed for a trip to the Moon! The space between Earth and the Moon can be represented as an N X M matrix, and each element's value is the amount of fuel the spaceship consumes when it passes through that space.

[Example]

To save on travel expenses, Jinwoo chose a rather unusual spaceship. The features of the spaceship he chose are as follows.

1. When going from Earth to the Moon, the directions in which the spaceship can move are as follows.

2. The spaceship cannot move in the direction it moved previously. That is, it cannot move in the same direction twice in a row.

Jinwoo's goal is to save as much fuel as possible while departing from any position on Earth and landing at any position on the Moon.

For Jinwoo, who wants to reach the Moon alive while spending as little money as possible, let us compute the minimum amount of fuel needed to reach the Moon.

Input

The first line gives N, M (2 ≤ N, M ≤ 1000), the size of the matrix representing the space between Earth and the Moon.

The next N lines give the values of the matrix elements. Each matrix element is a natural number no greater than 100.

Output

Print the minimum amount of fuel needed for the Moon trip.

Examples1

  1. Example 1

    Input
    6 4
5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58
    Expected output
    29