У Пака Чанека есть друг, который владеет киоском с напитками в столовой. Его друг продает напитки в течение \(n\) дней, начиная с дня \(1\) и заканчивая днем \(n\). Существует \(m\) видов напитков, пронумерованных от \(1\) до \(m\).
Прибыль от продажи напитка в конкретный день может быть разной. В день \(i\) прогнозируемая прибыль от продажи напитка типа \(j\) равна \(A_{i, j}\). Обратите внимание, что \(A_{i, j}\) может быть отрицательной, то есть продажа напитка фактически приведет к убыткам.
Пак Чанек хочет помочь своему другу спланировать продажи на \(n\) дней. В день \(i\) Пак Чанек должен выбрать для продажи как минимум один тип напитка. Более того, типы напитков, продаваемых в один день, должны образовывать подотрезок. Другими словами, в каждый день Пак Чанек будет выбирать \(i\) и \(j\) так, что \(1 \leq i \leq j \leq m\). Тогда будут проданы все виды напитков от \(i\) до \(j\) (включительно).
Однако для того, чтобы клиенты с предыдущего дня продолжали возвращаться, выбор типов напитков, проданных в день \(i\) (\(i>1\)), должен удовлетворять следующим условиям:
- Хотя бы один тип напитка, проданный в день \(i\), должен быть продан и в день \(i-1\).
- Хотя бы один тип напитка, проданный в день \(i\), должен не быть продан в день \(i-1\).
Дневная прибыль — это сумма прибылей от всех типов напитков, проданных в этот день. Общая прибыль по плану продаж — это сумма прибылей за \(n\) дней. Какую максимальную общую прибыль можно получить, если Пак Чанек оптимально спланирует продажи?
Примечание
Оптимальный план Пак Чанека:
- В день \(1\) Пак Чанек продаст напитки с \(1\) по \(3\). Прибыль составит \(79+20+49 = 148\).
- В день \(2\) Пак Чанек продаст напитки с \(2\) по \(4\). Прибыль составит \(9+109+24 = 142\).
- В день \(3\) Пак Чанек продаст напитки с \(1\) по \(6\). Прибыль составит \(185\).
Таким образом, общая прибыль плана Пак Чанека составит \(148 + 142 + 185 = 475\).