На ферме Goldilocks имеется N коров (1 <= N <=20,000), очень чувствительных к температуре.
Для каждой коровы указывается диапазон температур A(i)..B(i), которые допустимы. (0 <= A(i) <= B(i) <= 1,000,000,000). Если температура TB(i), то этой корове слишком жарко и она производит Z единиц молока. Y всегда больше чем и X, и Z.
По данным X Y Z а также наборам допустимых температур для каждой коровы, определите максимальное количество молока, которое может получить Goldilocks установкой оптимальной температуры (единой для всех коров).
Z Y Z – целые в диапазоне от 0 до 1000, а температура может быть установлена в любое целое значение.
Частичное оценивание: Из десяти тестов для этой задачи в тестах 1..4 B(i)<=100 для каждой коровы, и в тестах 1..6 значение N не превышает 1000.
PROBLEM NAME: milktemp
Формат входных данных
* Строка 1: Четыре разделённых пробелом целых числа: N X Y Z.
* Строки 2..1+N: Строка 1+i содержит два разделённых пробелом целых числа : A(i) B(i).
Формат выходных данных
* Строка 1: Максимальное количество молока, которое можно получить установкой оптимальной температуры в амбаре.
Примечание
Если установить температуру в 7 или 8, то коровам с номерами 1 и 4 будет комфортабельно, корове 2 будет жарко, а корове 3 – холодно. Всего будет произведено 31 единица молока.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 7 9 6
5 8
3 4
13 20
7 10
|
31
|