Задача J. Смесители
Задачу добавил: alef
Успешно сдано решений: 10
Время на тест 2 с, память 256 Мб
Для некоторых экспериментов необходимо получить довольно сложный химический раствор. Его нужно готовить в определенной последовательности, поэтому в отделе QQQ уже довольно давно придумали установку, состоящую из Q+1 резервуара, разделенных Q специальными заслонками. В каждом резервуаре происходит своя химическая реакция, после чего открывается очередная заслонка, и раствор продолжает свой путь. Вдоль резервуаров едет робот и поворачивает заслонки. Производство раствора занимает один день, и в течение этого дня робот перемещается от самого первого до последнего резервуара, последовательно поворачивая заслонки (каждую по одному разу).
Когда установку собирали, то делали ее из «подручных материалов»; в частности, многие заслонки были уже бывшими в употреблении и, соответственно, израсходовавшими часть своего ресурса. Некоторые старые заслонки уже вышли из строя и их заменили новыми, другой конструкции, — с практически неограниченным сроком эксплуатации.
Нужно сказать, что для поворота новых заслонок робот тратит H единиц энергии, а для поворота старых — 4*H. Но есть некоторая неприятность: если в линии присутствуют заслонки как старого, так и нового образца, роботу необходимо затрачивать еще P единиц энергии на каждое переключение между программами поворота. Считайте, что каждый день робот автоматически включается таким образом, что программа поворота настроена на поворот самой первой заслонки.
Замена старого вентиля на новый обходится в сумму R денежных единиц. Считайте также, что 1 единица энергии стоит 1 денежную единицу.
Товарищи ученые уговаривают завхоза заменить все старые заслонки. Однако товарищ завхоз очень экономный, и не хочет менять ни одну заслонку, пока она окончательно не выйдет из строя.
Но товарищи ученые не сдаются. Они подсчитывают «экономический эффект» для каждой из заслонок. Делают они это следующим образом. Предположим, на месте #J стоит старая заслонка, и известно, сколько поворотов она еще выдержит до конца эксплуатации. Ученые подсчитывают, каковы будут затраты, если заслонку не менять до тех пор, пока она не выйдет из строя (разумеется, при этом надо учитывать, что в течение этого времени могут выходить из строя другие старые заслонки, если они полностью исчерпали свой ресурс на количество поворотов до конца эксплуатации). А затем подсчитывают, каковы будут затраты, если заменить ее прямо сейчас. Если оказывается, что замена прямо сейчас приведет к экономии хотя бы одной денежной единицы, это уже повод поговорить с завхозом. Однако товарищ завхоз не очень верит ученым и соглашается на замену заслонки только в том случае, если ему предлагают заменить ту, которая выйдет из строя раньше всех. В один день завхоз соглашается заменить не более одной заслонки.
Ваша задача — определить, через сколько дней все старые заслонки будут заменены.
Формат входного файла input.txt
Первая строка — целые числа Q, Н, P, R, O (2 ≤ Q ≤ 10000, 1 ≤ O ≤ 10000,1 ≤ H, P ≤ 100, 1 ≤ R ≤ 1000) через пробел — количество заслонок, затраты энергии на поворот новой заслонки, затраты на переключение между программами поворота, стоимость замены заслонки, количество старых заслонок.
В каждой из следующих O строк содержится через пробел пара целых чисел: первое из диапазона от 1 до Q через пробел — номер старой заслонки, второе — положительное, не превосходящее 10000 — количество поворотов до выхода из строя соответствующей заслонки.
Гарантируется, что у всех старых заслонок попарно различное количество поворотов до выхода из строя.
Формат выходного файла output.txt
Первая строка — целое число — количество дней, спустя которые все старые заслонки будут заменены.
Пример входного файла
10 2 3 25 6
8 4
10 12
1 8
4 6
9 17
6 11
Пример выходного файла
13