Дан квад­рат 15 × 15 кле­ток, в каж­дой клет­ке ко­то­ро­го за­пи­са­но целое число. В левом верх­нем углу квад­ра­та стоит ладья. За один ход ладья может пе­ре­ме­стить­ся в пре­де­лах квад­ра­та на любое ко­ли­че­ство кле­ток впра­во или вниз (влево и вверх ладья хо­дить не может). Не­об­хо­ди­мо пе­ре­ме­стить ладью в пра­вый ниж­ний угол так, чтобы сумма чисел в клет­ках, в ко­то­рых ладья оста­нав­ли­ва­лась (вклю­чая на­чаль­ную и ко­неч­ную), была мак­си­маль­ной. В от­ве­те за­пи­ши­те мак­си­маль­но воз­мож­ную сумму.

Ис­ход­ные дан­ные за­пи­са­ны в элек­трон­ной таб­ли­це.

При­мер вход­ных дан­ных (для таб­ли­цы раз­ме­ром 4 × 4):

Для ука­зан­ных вход­ных дан­ных от­ве­том будет число 14 (ладья про­хо­дит через клет­ки с чис­ла­ми −3, 6, 1, 7, 6, −3).