Приватні інтереси#7205
На клітинках прямокутної таблиці, що має рядків та стовпчиків, розкладено монети. Двоє гравців по черзі рухають пішак або праворуч, або вгору на одне поле за один хід. Гру розпочинає перший гравець з крайнього нижнього лівого поля. Гру припиняють після досягнення пішаком першого (якщо рахувати згори вниз) рядка чи останнього (якщо рахувати зліва направо) стовпчика таблиці. Кожен гравець:
не має можливості спілкуватися з суперником;
знає розподіл монет перед початком гри;
знає розташування пішака у будь-який момент гри;
забирає монети з клітин, на які ставить пішак;
намагається отримати найбільшу суму грошей за всю гру;
ходить праворуч лише тоді, коли хід вгору приносить менший остаточний зиск;
знає і враховує намагання суперника;
знає, що суперник діє аналогічно.
Створіть програму, яка передбачить результат гри та рух пішака.
Перший рядок містить у вказаному порядку натуральні числа та . Для в межах від до включно (j + 1)-ий рядок містить невід'ємні цілі числа - сукупні вартості монет у клітинках -го рядка таблиці в тому порядку, як вони (клітинки цього рядка) розташовані в таблиці зліва направо. Кількість всіх чисел не перевищує , максимальний виграш не перевищує (золотих).
Перший рядок має містити два невід'ємних цілих числа - виграші (кількості зібраних монет) першого та другого гравців відповідно.
Другий рядок має містити послідовність символів, що описують напрям ходів пішака (від першого до останнього) для досягнення цього результату: u - вгору (від англійського up), r - праворуч (від англійського right).
Приклад 1