A scree slope is modeled as a grid of R rows and C columns; each cell holds an integer weight (which may be negative). A rock is released from any single cell in the top row and falls to the bottom row. From cell (r, c) it moves to one of (r+1, c-1), (r+1, c), or (r+1, c+1), provided that cell stays within the grid. The total of a fall is the sum of every cell it occupies, including the starting top-row cell and the final bottom-row cell.

Over every choice of starting column and every valid sequence of moves, determine the minimum possible total.

Input format

Line 1: two integers R and C. Next R lines: each contains C integers, the weights of that row.

Output format

A single integer: the minimum total of a fall from the top row to the bottom row.

Constraints

• 1 <= R <= 100
• 1 <= C <= 100
• -1000 <= each weight <= 1000

3 3
2 1 3
6 5 4
7 8 9

13

1 3
4 2 6

2