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

Шаг впра­во раз­ре­ша­ет­ся сде­лать толь­ко в клет­ку с чис­лом той же чётно­сти, шаг вниз  — толь­ко в клет­ку с чис­лом дру­гой чётно­сти. Шаг по диа­го­на­ли воз­мо­жен все­гда.

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

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

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

При ука­зан­ных вход­ных дан­ных мак­си­маль­ное зна­че­ние 250 по­лу­чит­ся при дви­же­нии по марш­ру­ту 53 → 63 → 62 → 59 → 13. Не­до­ступ­ны для ро­бо­та клет­ки с чис­ла­ми 18, 80, 2, 86  — всего 4 клет­ки. В от­ве­те в дан­ном слу­чае надо за­пи­сать числа 250 и 4.

Ответ: