У давньому королівстві лицару за добру службу дали можливість пройти через королівську скарбницю і забрати стільки золотих монет, скільки є в тих кімнатах, через які він буде проходити. Лицар добув план скарбниці і встановив, що вона складається з ~n~ рядів по ~m ~кімнат у кожному. З кожної кімнати ведуть троє дверей до кімнат нижнього ряду (нижньої і двох сусідніх до неї). Кожні двері відчиняються тільки в одному напрямі, тобто повернутися назад неможливо. Лицар може почати рух з будь-якої верхньої кімнати (першого ряду). Відомо, скільки монет знаходиться в кожній кімнаті. Яку максимальну кількість монет може винести лицар із скарбниці?

Формат вхідних даних

У першому рядку дано два цілих числа ~n, m~ ~(1 ≤ n, m ≤ 100)~ – розміри скарбниці.

У наступних ~n~ рядках дано ~m~ цілих чисел ~a[i,j]~ – кількість монет, що знаходиться у кімнаті у ~i~-му рядку і ~j~-му стовпці ~(0 ≤ a[i,j] ≤ 100)~.

Формат вихідних даних

Максимальну кількість монет, що може винести із скарбниці лицар.

Приклад вхідних даних

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

Приклад вихідних даних

24