Робот стоит в левом верх­нем углу пря­мо­уголь­но­го поля, в каж­дой клет­ке ко­то­ро­го за­пи­са­но целое по­ло­жи­тель­ное число. За один ход робот может пе­ре­ме­стить­ся на одну клет­ку впра­во, вниз или по диа­го­на­ли впра­во вниз.

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

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

В от­ве­те за­пи­ши­те два числа: сна­ча­ла мак­си­маль­но воз­мож­ное зна­че­ние, затем ми­ни­маль­но воз­мож­ное.

Ис­ход­ные дан­ные за­пи­са­ны в элек­трон­ной таб­ли­це. При­мер вход­ных дан­ных (для таб­ли­цы раз­ме­ром 4 × 4):

При ука­зан­ных вход­ных дан­ных мак­си­маль­ное зна­че­ние 303 по­лу­чит­ся при дви­же­нии по марш­ру­ту 43 → 49 → 52 → 83 → 22 → 85 →R 9; 74, а ми­ни­маль­ное зна­че­ние 141 при дви­же­нии по марш­ру­ту 43 → 49 → 8 → 22 → 74. В от­ве­те в дан­ном слу­чае надо за­пи­сать числа 303 и 141.

Ответ:

Робот стоит в левом ниж­нем углу пря­мо­уголь­но­го поля, в каж­дой клет­ке ко­то­ро­го за­пи­са­но целое по­ло­жи­тель­ное число. За один ход робот может пе­ре­ме­стить­ся на одну клет­ку впра­во, вверх или по диа­го­на­ли впра­во вверх.

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

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

В от­ве­те за­пи­ши­те два числа: сна­ча­ла мак­си­маль­но воз­мож­ное зна­че­ние, затем ми­ни­маль­но воз­мож­ное.

Ис­ход­ные дан­ные за­пи­са­ны в элек­трон­ной таб­ли­це. При­мер вход­ных дан­ных (для таб­ли­цы раз­ме­ром 4 × 4):

При ука­зан­ных вход­ных дан­ных мак­си­маль­ное зна­че­ние 311 по­лу­чит­ся при дви­же­нии по марш­ру­ту 36 → 97 → 49 → 52 → 83 → 64 → 35, а ми­ни­маль­ное зна­че­ние 83 при дви­же­нии по марш­ру­ту 36 → 7 → 8 → 52 → 25 → 35.

В от­ве­те в дан­ном слу­чае надо за­пи­сать числа 311 и 83.

Ответ: