eolymp
bolt
Try our new interface for solving problems
Məsələlər

Черепахоконь

Черепахоконь

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Дана клетчатая доска n × m в каждой клетке которой записано натуральное число. В верхнем левом углу доски сидит черепашка. Черепашка умеет делать ход конём по направлению вниз и вправо. То есть либо перемещаться на одну клетку вправо и на две клетки вниз, либо на одну клетку вниз и на две клетки вправо. Помогите черепашке добраться в правый нижний угол доски, собрав максимальную сумму чисел. Считается, что черепашка собирает только те числа, на которых завершает ход, а не все, по которым проползает.

Giriş verilənləri

В первой строке находятся два целых числа n и m (1n, m100), задающие размеры доски. Далее следуют числа, записанные на доске - n строк по m положительных чисел, не превышающих 10000.

Çıxış verilənləri

Выведите одно число, равное искомой максимальной сумме, либо -1, если черепашка не может добраться до правого нижнего угла.

Nümunə

Giriş verilənləri #1
2 3
3 2 7
1 9 5
Çıxış verilənləri #1
8