Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Основное занятие жителей Трантора -- имперской столицы -- это освоение бюджетов.
Ежегодно Имперское Министерство Счастья выделяет деньги на различные проекты,
каждый из которых требует определенной суммы денег, делает счастливыми некоторое
количество людей и завершается в конце года. Сумма затрат по всем проектам не должна превышать годового бюджета
Министерства. Если бюджет потрачен полностью, то в следующем году его величина остается такой же, как в текущем. Но
если бюджет на год равен `X`, а потрачена в течение года меньшая сумма `Y`, то за неполное освоение средств Министерство наказывают: доступный
бюджет на следующий год уменьшается на `2*(X-Y)` (или даже полностью обнуляется,
если потрачена только половина бюджета или меньше). Император приказывает вам осчастливить максимальное количество людей за время вашей работы.
В первой строке вводятся 3 целых числа: бюджет Министерства в первый год `B` (`1<=B<=100`, в гигакредитах), количество
проектов `N` (`1<=N<=10^5`) и горизонт планирования `T` (`1<=T<=10^3`, в годах). Затем следует `N` строк, по два целых числа в каждой, описывающих
возможные проекты: сумма расходов на проект `C_i` (`1<=C_i<=B`, в гигакредитах) и количество людей `H_i` (`0<=H_i<=10^4`), которых финансирование проекта
делает счастливыми за год. Набор возможных проектов не меняется год от года, но распределение
финансирования можно менять. Любой проект должен быть в течение года профинансирован полностью, либо не профинансирован
вообще (иначе вы будете привлечены к ответственности за нецелевое использование средств).
Выведите одно целое число -- максимальное общее количество людей, которых Министерство может сделать счастливыми за `T` лет работы.
```sample Пример ввода
100 2 3
60 10000
10 1000
```
```sample Пример вывода
12000
```
Пояснение к примеру. В первый год мы можем профинансировать оба проекта, сделав
счастливыми `10000+1000=11000` людей и потратив `60+10=70` гигакредитов. Значит, 30 гигакредитов останутся
не потраченными, и бюджет на второй год будет равен `100-2*30 = 40` гигакредитов. Во второй год мы сможем профинансировать
только второй проект и сделать счастливыми еще 1000 человек. При этом мы потратили меньше
половины от текущего бюджета (10 из 40 гигакредитов), поэтому на третий год бюджет полностью обнулится.
Начало
Рабочее место участника
Динамическое программирование и запоминающие функции