Jinwoo's Moon Trip (Small)

Interview

Time limit1sMemory limit256 MB

Summary
Given an N by M grid of fuel costs with N, M at most 6, find the minimum cost path from any cell in the top row to any cell in the bottom row, where each step moves downward and no two consecutive steps use the same direction.
Level

Medium6 of 10

Topics
Dynamic programming, Matrix, Implementation
Solved
No attempts yet

Problem

Jinwoo, who dreamed of spaceflight, worked hard at the restaurant 'Fresh Every Day' and finally 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 is the amount of fuel the spacecraft consumes when it passes through that cell.

[Example]

To save on travel expenses, Jinwoo chose a rather unusual spacecraft. Its features are as follows.

1. When traveling from Earth to the moon, the directions in which the spacecraft can move are as shown below.

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

Jinwoo's goal is to start from any position on Earth and land at any position on the moon while saving as much fuel as possible.

For Jinwoo, who wants to reach the moon while saving money, compute the minimum amount of fuel needed to reach the moon.

Input

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

The next N lines give the elements of the matrix. Each 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