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

Не решаласьСредняя

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

Есть $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 монеты.

$5 * 1 + 4 * 3 + 2 * 2 = 21$

Ограничения

Ограничение времени

2 с

Ограничение памяти

256 МБ

Пример 1

Ввод
2 4 3
5 1
2 2
4 3
1 3
Вывод
21

Теги

Нужно войти, чтобы отправить решение.Войти