Try our new interface for solving problems

Turtle Knight

Turtle Knight

The chessboard of size n × m is given. Each its cell contains a positive integer. The turtle sits in the upper left corner. The turtle can make knight moves down and right. That is, it can move either one step to the right and two steps down, or one step down and two steps to the right. Help the turtle to reach the lower right corner of the board, collecting the maximum sum of numbers. The turtle collects only those numbers, where it finishes its moves, but not all where it creeps.


First line contains two integers n and m (1n, m100) giving the size of the board. Then given numbers written on the board - n rows each containing m positive integers, not greater than 10000.


Print the desired maximum sum , or -1 if the turtle can't reach the lower right corner.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2 3
3 2 7
1 9 5
Output example #1