Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Подготовка к экзамену - 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

Сдать задачу

Задать вопрос жюри по этой задаче