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

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

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

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

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

При ука­зан­ных вход­ных дан­ных мак­си­маль­ное зна­че­ние 147 по­лу­чит­ся при дви­же­нии по марш­ру­ту 6 → 50 → 49 → 11 → 31. Не­до­ступ­ны для ро­бо­та клет­ки с чис­ла­ми 61, 15, 12, 17, 53  — всего 5 кле­ток. В от­ве­те в дан­ном слу­чае надо за­пи­сать числа 147 и 5.

Ответ: