У давньому королівстві лицару за добру службу дали можливість пройти через королівську скарбницю і забрати стільки золотих монет, скільки є в тих кімнатах, через які він буде проходити. Лицар добув план скарбниці і встановив, що вона складається з \(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