Задача E. Путь
Задачу добавил: alef
Успешно сдано решений: 8
В письме купца было сказано - "Я не могу подарить тебе перстень, о великий царь, но ты получил то, что пожелал". С той ночи, когда купец надел Елисею перстень на руку, Елисей больше не спал. Поначалу ему это нравилось, но вскоре он стал замечать, что устает с каждым днем все больше и больше. Силы оставляли его, но не было у него отдыха. Друзья Елисея сбились с ног, приводили к нему разных лекарей со всего тридевятого царства, и с соседних государств, но никакие снадобья царю не помогали. И тогда несколько его друзей отправились в дальнее путешествие, в надежде найти лекарство для царя. Долго ли, коротко ли, но добрались они до страны Кам-Куру, и повстречали лекаря Лисандера. Выслушав историю, приключившуюся с Елисеем, сказал им Лисандер:- Лекарствами болезни лечат, а заклятье снимать - иное умение надобно. За этим нужно обратиться к магу Ормусу. Живет он посреди пустыни, и добраться до него нелегко.
Наутро друзья стали собираться в путь, а Лисандер приготовил для них карту, на которой он обозначил колодцы. Запас воды в каждом колодце зависит от времени суток. С полуночи до полудня вода накапливается - каждый час D единиц объема воды, а с полудня до полуночи она испаряется с такой же скоростью, и в полночь объем воды в колодце достигает минимума - Q единиц.
- Идти следует строго от колодца к колодцу. В течение одного часа каждому нужно обязательно выпить единицу объема воды, - наставлял друзей Лисандер. - Доберетесь до колодца - наберите воды столько, сколько будет возможно. И торопитесь - скоро начнется песчаная буря!
Известно, за сколько часов каждый из путников может преодолеть единицу расстояния по пустыне. Группа путников двигается со скоростью самого медленного из них. У каждого из путников есть фляга некоторой емкости. В дороге путники могут делиться водой друг с другом и не делают остановок. По совету Лисандера они собираются отправиться в путь ровно в полночь.
Нужно выяснить, какое максимальное количество человек может пойти к жилищу Ормуса, и сколько времени займет у них это путешествие.
Формат входного файла input.txt
Первая строка - целые числа N и K через пробел. N (1<=N<=100)- количество друзей Елисея, K - количество колодцев (0 <= K <= 100).
Каждая из следующих N строк содержит по два целых числа через пробел - Aj и Tj (1 <= Aj, Tj <= 10^6, j = 1, 2, ..., N), где Aj - емкость фляги, принадлежащей путнику #j, в единицах объема, а Tj - время (в часах), за которое путник #j может преодолеть единицу расстояния.
В строке N+2 содержится K+1 целых чисел P0, P1, P2, ... PK через пробел. Pm (1 <= Pm <= 10^6, m = 0, 1, 2, ..., K) - расстояние (в единицах расстояния) от колодца #m до следующего. P0 - расстояние от границы пустыни (точки старта друзей) до 1го колодца, PK - расстояние от колодца #K до жилища Ормуса.
В последней строке - два целых числа Q и D через пробел. Q (0 <= Q <= 10^6)- количество воды в колодце в полночь, D (0 <= D <= 10^6) - количество воды, которое прибывает (с полуночи до полудня) или убывает (с полудня до полуночи) в течение часа в колодце.
Изначально все фляги заполнены водой.
Примечания. Путник может отправиться в путь только со своей флягой. От полуночи до полуночи проходит ровно 24 часа.
Формат выходного файла output.txt
Первая строка - целые числа M и Т через пробел. M - максимальное количество друзей, которые могут отправиться в путь до жилища Ормуса. T - время, которое займет у них путь. Если существует несколько решений с одинаковыми M, выведите то, в котором T минимально.
Пример входного файла
10 0
53 40
4 75
12 63
78 49
64 60
50 29
63 80
86 30
95 58
60 67
1
0 0
Пример выходного файла
7 67