Candy Picking Contest

Time limit1sMemory limit256 MB

Summary

Choose boxes in an M by N grid so no two chosen boxes touch vertically or horizontally, maximizing the total candies collected.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Array, Matrix
Solved: No attempts yet

Problem

Sangkeun is a boy who loves candy. He is an avid subscriber of Candy Magazine, and this year he represents Korea at the International Candy Picking Contest.

The contest takes place where boxes of candy are arranged in a grid of $M$ rows and $N$ columns, so there are $M \times N$ boxes in total. The number of candies inside each box is written on its outside.

A contestant chooses one box and takes all of the candies inside it. Whenever a box is chosen, the candies in the boxes at the following positions disappear:

every box in the row immediately above the chosen box,
every box in the row immediately below the chosen box,
the box immediately to the left and the box immediately to the right of the chosen box, in the same row.

The contestant may keep choosing boxes until no box with any candy remains.

Given $M$ , $N$ , and the number of candies in every box, write a program that finds the maximum number of candies Sangkeun can take.

Input

The input consists of several test cases. The first line of each test case contains two integers $M$ and $N$ ( $1 \le M \times N \le 10^5$ ). Each of the next $M$ lines contains the $N$ candy counts of the boxes in that row, separated by spaces. Every box contains at least $1$ and at most $10^3$ candies.

The last line of the input contains two zeros and must not be processed.

Output

For each test case, print on its own line the maximum number of candies Sangkeun can take.

Examples1

Example 1

Input

5 5
1 8 2 1 9
1 7 3 5 2
1 2 10 3 10
8 4 7 9 1
7 1 3 1 6
4 4
10 1 1 10
1 1 1 1
1 1 1 1
10 1 1 10
2 4
9 10 2 7
5 1 1 5
0 0

Expected output

54
40
17