258. Максимизация прибыли

Рассмотрим задачу менеджера рекламного агентства.

Есть $n$ билбордов, на которых можно размещать рекламные объявления. Планирование размещения проводится на $w$ недель вперед. Модель размещения рекламы разрешает сохранить одно и тоже объявление несколько недель на одном билборде, перенести объявление на следующей неделе на другой билборд. Размещать одно объявление на разных, не обязательно последовательных, неделях будущего периода. Однако на одной неделе не может быть рекламных объявлений от одного рекламодателя на разных билбордах. $\newline$ $k$ рекламодателей хотят разместить рекламу. Заявки подают рекламодатели в формате аукциона, но не знают заявок конкурентов. Известно, что $i$-й рекламодатель подал заявку на размещение своей рекламы максимум на $w_i$ недель с оплатой $c_i$ за каждую неделю размещения, т.е. рекламное объявление $i$-го рекламодателя может быть размещено от 0 до $w_i$ в течение периода (при размещении рекламы в течение $m$ недель оплата за нее составит $m \cdot c_i$).

Менеджеру нужно выбрать, в какие недели и на каких билбордах разместить рекламу рекламодателей.

Требуется максимизировать прибыль от размещения рекламы.

Первая строка содержит три разделенных пробелом числа $n$, $k$ и $w$ ($1 \leq n \leq 10^3, 1 \leq k \leq 10^5, 1 \leq w \leq 10^2$).

Далее идет $k$ строк. Каждая строка содержит два разделенных числа — $c_i$ и $w_i$ ($1 \leq c_i \leq 10^2$, $1 \leq w_i \leq w$).

Вывод должен состоять из одного числа $max \_ profit$ — ответ на задачу.

В первом примере распределение может выглядеть таким образом:

[1; 3; 3]

[3; 2; 2], 

где первый рекламодатель платит нам 5 монет за неделю, 3-ий — 4 монеты и 2-ой — 2 монеты.