| Автор: | Жюри всероссийских зимних сборов школьников 2007-2008 | Ограничение времени: | 2 сек | |
| Входной файл: | holidays.in | Ограничение памяти: | 64 Мб | |
| Выходной файл: | holidays.out | |||
| Максимальный балл: | 100 |
В огромной международной компании работает n программистов. Все программисты работают удаленно, а общаются только по телефону или ICQ. Проблема состоит в том, что все они живут в разных странах. В этих странах разные традиции и разные праздники. Компания уважает государственные праздники всех своих сотрудников, поэтому не может заставлять их выходить на работу в такие дни. Сейчас перед советом директоров фирмы стоит задача назначить одного из программистов руководителем проекта. Но если руководитель приходит на работу и не может связаться с одним из своих сотрудников (так как у него выходной), то он недоволен.
Если он не может связаться более, чем с k сотрудниками, то руководитель просто приходит в ярость. Скажем, что степень недовольства в некоторый рабочий день руководителя вычисляется как количество сотрудников, с которыми он не может связаться. Если руководитель приходит в ярость, то степень его недовольства в этот день равна 10 ⋅ k.
Совет директоров принял решение, что руководителем проекта нужно назначить человека, суммарная степень недовольства которого за все время работы будет минимальным. (Главное — моральное состояние сотрудников. Совершенно не важна квалификация руководителя). Несмотря на то, что в фирме огромное количество программистов высокого уровня, которые бы с легкостью справились с этой задачей, никому из них нельзя доверить ее решение, так как они заинтересованы стать руководителями проекта сами. Поэтому решение этой задачи поручается независимому эксперту, то есть Вам.
1 ≤ n, k ≤ 105
0 ≤ p ≤ 105
1 ≤ l ≤ r ≤ 105
Суммарное количество отрезков не превосходит 105.
Все числа во входном файле целые.
| № | Входной файл (holidays.in) |
Выходной файл (holidays.out) |
|---|---|---|
| 1 | |
|
| 2 | |
|