Робот стоит в левом верх­нем углу пря­мо­уголь­но­го поля, в каж­дой клет­ке ко­то­ро­го за­пи­са­но на­ту­раль­ное число. За один ход робот может пе­ре­ме­стить­ся на одну клет­ку впра­во или на одну клет­ку вниз. Вы­хо­дить за пре­де­лы поля робот не может. В на­чаль­ный мо­мент запас энер­гии ро­бо­та равен числу, за­пи­сан­но­му в стар­то­вой клет­ке. После каж­до­го шага ро­бо­та запас энер­гии из­ме­ня­ет­ся по сле­ду­ю­щим пра­ви­лам: если число в оче­ред­ной клет­ке боль­ше, чем в преды­ду­щей, запас уве­ли­чи­ва­ет­ся на ве­ли­чи­ну этого числа, если мень­ше  — умень­ша­ет­ся на эту же ве­ли­чи­ну.

Опре­де­ли­те мак­си­маль­ный и ми­ни­маль­ный запас энер­гии, ко­то­рый может быть у ро­бо­та после пе­ре­хо­да в пра­вую ниж­нюю клет­ку поля. В от­ве­те за­пи­ши­те два числа: сна­ча­ла мак­си­маль­но воз­мож­ное зна­че­ние, затем ми­ни­маль­ное.

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

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

При ука­зан­ных вход­ных дан­ных мак­си­маль­ное зна­че­ние по­лу­ча­ет­ся при дви­же­нии по марш­ру­ту 200 − 8 + 69 − 7 + 17 + 32 + 43  =  346, а ми­ни­маль­ное при дви­же­нии по марш­ру­ту 200 − 87 − 35 − 7 + 9 + 80 − 43  =  117.

Ответ:

Робот стоит в левом верх­нем углу пря­мо­уголь­но­го поля, в каж­дой клет­ке ко­то­ро­го за­пи­са­но на­ту­раль­ное число. За один ход робот может пе­ре­ме­стить­ся на одну клет­ку впра­во или на одну клет­ку вниз. Вы­хо­дить за пре­де­лы поля робот не может. В на­чаль­ный мо­мент запас энер­гии ро­бо­та равен числу, за­пи­сан­но­му в стар­то­вой клет­ке. После каж­до­го шага ро­бо­та запас энер­гии из­ме­ня­ет­ся по сле­ду­ю­щим пра­ви­лам: если число в оче­ред­ной клет­ке мень­ше, чем в преды­ду­щей, запас уве­ли­чи­ва­ет­ся на ве­ли­чи­ну этого числа, если боль­ше  — умень­ша­ет­ся на эту же ве­ли­чи­ну.

Опре­де­ли­те мак­си­маль­ный и ми­ни­маль­ный запас энер­гии, ко­то­рый может быть у ро­бо­та после пе­ре­хо­да в пра­вую ниж­нюю клет­ку поля. В от­ве­те за­пи­ши­те два числа: сна­ча­ла мак­си­маль­но воз­мож­ное зна­че­ние, затем ми­ни­маль­ное.

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

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

При ука­зан­ных вход­ных дан­ных мак­си­маль­ное зна­че­ние по­лу­ча­ет­ся при дви­же­нии по марш­ру­ту 200 + 87 + 35 + 7 − 9 − 80 + 43  =  283, а ми­ни­маль­ное при дви­же­нии по марш­ру­ту 200 + 8 − 69 + 7 − 17 − 32 − 43  =  54.

Ответ: