eolymp
bolt
Try our new interface for solving problems
Problems

Turtle Knight

Turtle Knight

Time limit 1 second
Memory limit 128 MiB

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.

Input data

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.

Output data

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

Examples

Input example #1
2 3
3 2 7
1 9 5
Output example #1
8