Задача №114121. Билеты на поезд
Вот-вот стартует заключительный этап Открытой олимпиады школьников, и преподавателям из других городов пора задуматься об отправлении детей к месту проведения олимпиады. Конечно же, легче всего добраться до Москвы на поезде, но для этого надо озаботиться покупкой билетов. Именно с этой задачей сегодня столкнулся Денис — ответственный за олимпиады по программированию в замечательном городе Кислозаводске. Внимательно изучив расписание поездов, он пришел к выводу, что удобнее всего будет добираться на фирменном поезде «Капкан», ходящим напрямую из Кислозаводска в Москву. К сожалению, данный состав ходит не чаще двух раз в неделю, поэтому Денис выбрал конкретный рейс, на котором поедут все школьники.
Так исторически сложилось, что все вагоны поезда имеют разную вместимость. Кроме того, вагоны отличаются условиями комфорта, поэтому цены на билет в разные вагоны тоже отличаются. Все места внутри одного вагона стоят одинаково.
По результатам отборочного этапа \(n\) учеников из данного города прошли на заключительный этап, и естественно, Денис хочет потратить как можно меньше денег на билеты. Сначала эта задача показалась ему очень простой, но потом Денис вспомнил про введённый недавно закон, гласящий, что детей в столь длительных поездках должны сопровождать взрослые. Кроме того, закон строго регламентирует необходимое количество взрослых для присмотра за группой детей, на каждые \(k\) школьников нужен хотя бы один взрослый сопровождающий. Стоит отметить, что взрослый может присматривать только за детьми из того же вагона, что и он сам. Более формально, если в вагоне едут \(x\) детей, то в этом же вагоне должны находиться хотя бы \(\left \lceil{\frac{x}{k}}\right \rceil\) взрослых. При этом Денис может уговорить на участие в поездке сколь угодно много сопровождающих, так что по этому параметру ограничений нет. Разумеется, за билеты для сопровождающих тоже нужно платить.
Теперь перед Денисом стоит куда более сложная задача, помогите ему справиться с ней как можно быстрее: отправить всех детей и необходимое количество взрослых на олимпиаду данным поездом, не нарушая при этом закон и потратив минимально возможное количество денег. Если невозможно отправить всех детей и нужное количество взрослых данным поездом, то выведите « -1 ». В противном случае выведите ответ — минимальную суммарную стоимость всех билетов.
В первой строке входных данных записаны три целых целых числа \(m\), \(n\) и \(k\) (\(1 \leq m \leq 10^6\), \(0 \leq n \leq 10^9\), \(1 \leq k \leq 20\)) — количество вагонов в поезде, количество детей, прошедших на заключительный этап, и максимальное количество детей на одного сопровождающего.
В следующих \(m\) строках записаны по два целых числа \(p_i\) и \(c_i\) (\(1 \leq p_i, c_i \leq 10^9\)) — количество свободных мест и стоимость одного места в \(i\)-м вагоне.
Выведите одно число — минимальную суммарную стоимость билетов, которую необходимо потратить для отправления всех школьников, или « -1 », если всех детей отправить невозможно.
Обратите внимание, что билет Денису покупать не нужно, он предпочитает путешествовать на велосипеде.
В первом тесте из условия оптимальным способом будет отправить 4 детей с 2 взрослыми в третьем вагоне, 6 детей с 2 взрослыми в пятом вагоне и 2 детей с 1 взрослым во втором вагоне. Таким образом, в каждом вагоне на каждых трёх детей будет хотя бы один взрослый, а общая стоимость поездки составит \(6 \cdot 2 + 8 \cdot 5 + 3 \cdot 6 = 12 + 40 + 18 = 70\).
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
5 12 3 10 7 11 6 6 2 7 10 8 5
70
8 55 1 70 22 69 9 99 44 31 81 57 50 22 79 99 33 17 64
1536