Личные интересы
На клетках прямоугольной таблицы размером m на n разложены монеты. Двое игроков по очереди передвигают пешку либо вправо, либо вверх на одно поле за ход. Первый игрок начинает игру с крайнего нижнего левого угла. Игра заканчивается, когда пешка достигает верхнего ряда или последнего столбца таблицы. Каждый игрок:
не может общаться с соперником;
знает распределение монет до начала игры;
всегда осведомлён о текущем положении пешки;
забирает монеты с клеток, на которые ставит пешку;
стремится собрать максимальную сумму монет за игру;
выбирает движение вправо только если ход вверх приносит меньший выигрыш;
учитывает стратегию соперника;
знает, что соперник действует аналогично.
Напишите программу, которая предскажет итог игры и траекторию движения пешки.
Входные данные
Первая строка содержит натуральные числа m и n. Для каждого j от 1 до m включительно, (j + 1)-ая строка содержит неотрицательные целые числа — стоимости монет в клетках j-го ряда, расположенных слева направо. Общее количество чисел не превышает 12346, а максимальный выигрыш не превышает 65432 (золотых).
Выходные данные
Первая строка должна содержать два неотрицательных целых числа — выигрыши (суммы собранных монет) первого и второго игроков соответственно.
Вторая строка должна содержать последовательность символов, описывающих направление ходов пешки (от первого до последнего) для достижения этого результата: u — вверх (от английского up), r — вправо (от английского right).