Алиса и Боб играют в игру на матрице, состоящей из \(2\) строк и \(m\) столбцов. В ячейке в \(i\)-й строке в \(j\)-м столбце лежит \(a_{i, j}\) монет.
Изначально Алиса и Боб стоят в ячейке \((1, 1)\). Они собираются пройти какой-то последовательностью ходов в ячейку \((2, m)\).
Возможные ходы следующие:
- Пойти направо — из некоторой ячейки \((x, y)\) в \((x, y + 1)\);
- Пойти вниз — из некоторой ячейки \((x, y)\) в \((x + 1, y)\).
Сначала Алиса делает все свои ходы, пока не достигнет \((2, m)\). Она собирает монеты во всех клетках, которые они посещает (включая стартовую).
Когда Алиса заканчивает, Боб начинает свой путь. Он также делает ходы, чтобы достичь \((2, m)\), и собирает монеты во всех клетках, которые он посетил, а Алиса нет.
Счет в игре равен суммарному количеству монет, которые собрал Боб.
Алиса хочет минимизировать счет. Боб хочет максимизировать счет. Какой будет счет в игре, если оба игрока играют оптимально?