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

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

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

Для ука­зан­ных вход­ных дан­ных оп­ти­маль­ным марш­ру­том будет путь по клет­кам 44, 42, 89, 50, 26, 70, 85. Ито­го­вая сумма равна 44 + 89 + 70 + 85  =  288. Числа 42, 50 и 26 не вклю­ча­ют­ся в сумму, так как 42 < 44, 50 < 89 и 26 < 50.