Подготовка к экзамену - II
Задачу добавил: elena
Успешно сдано решений: 2
На экзамене при подготовке теоретических вопросов разрешается пользоваться любой литературой. Поскольку Кеша перед экзаменом занимался только решением задач, и не успел выучить ни одного теоретического вопроса, он собирается взять с собой несколько книг из имеющихся у него F книг по данному предмету.
В списке N экзаменационных вопросов. Для каждой книги #j известно, что в ней содержатся ответы на вопросы с Qj1 по Qj2 (без "пропусков"). Кроме того, известно, что курс построен очень логично и, зная вопрос #i, можно без использования книг за d минут получить ответ на вопрос #(i+1) (ответ на вопрос #(i+2) из вопроса #i можно получить за 2*d минут, и т.д.).
В билете содержится два теоретических вопроса. На подготовку к ответу по билету дается t минут. Кеша хочет принести с собой минимально возможное количество книг, чтобы успешно подготовиться к ответу по билету на экзамене.
Ваша задача - определить, какое минимально возможное количество книг ему придется взять с собой?
Формат входного файла input.txt
Первая строка содержит целые числа N и F через пробел (1<=N<=1000, 0<=F<=1000); N - количество экзаменационных вопросов, F - количество книг, имеющихся у Кеши.
Вторая строка содержит целые числа d и t через пробел (1<=d<=10000, 0<=t<=10000); d - время, которое требуется на подготовку ответа на вопрос, исходя из предыдущего, t - время, которое дается на подготовку по билету.
Каждая из следующих F строк (с 3-ей по F+2-ую) содержит по два целых числа через пробел: Qj1 и Qj2 (1<=Qj1<=Qj2<=N) - номер в списке соответственно первого и последнего из вопросов, содержащегося в книге с соответствующим номером.
Формат выходного файла output.txt
Первая строка - целое число - минимально возможное количество книг, которые Кеше необходимо взять с собой, чтобы сдать экзамен, либо слово NO, если задача не имеет решения.
Пример входного файла
10 2
5 15
1 9
2 5
Пример выходного файла
1