Мальчик Валера зарегистрировался на сайте Codeforces под ником Valera и написал свой первый Codeforces Round #300. Он похвастался другу Аркадию, что за свое первое соревнование набрал целых x баллов. Но Аркадий не поверил на слово другу и решил проверить, действительно ли Валера мог показать такой результат.
Он знает, что соревнование под номером 300 было необычным, поскольку в нем было всего две задачи. Соревнование длилось t минут, минуты нумеруются с нуля. Первая задача имела начальную стоимость a баллов, и каждую минуту эта стоимость уменьшалась на da баллов. Вторая задача имела начальную стоимость b баллов, и каждую минуту эта стоимость уменьшалась на db баллов. Таким образом, как только закончится нулевая минута соревнования, первая задача будет стоить a - da баллов, а вторая — b - db баллов. Гарантируется, что в любую минуту соревнования каждая задача имеет неотрицательную стоимость.
Аркадий просит Вас узнать, мог ли Валера получить за это соревнование ровно x баллов. При этом стоит считать, что Валера мог решить любое количество из предложенных задач. Также следует считать, что по каждой задаче Валера сделал не более одной попытки, причем обе задачи он мог отправить на проверку в одну и ту же минуту соревнования, начиная с минуты под номером 0 и заканчивая минутой под номером t - 1. Обращаем внимание, что посылать решение ровно через t минут после начала соревнование Валера не может.
Выходные данные
Если Валера мог набрать за соревнование ровно x баллов выведите «YES», в противном случае выведите «NO» (без кавычек).
Примечание
В первом примере Валера мог поступить следующим способом: первую задачу сдать на минуте под номером 0, вторую задачу сдать на минуте под номером 2. Тогда за первую задачу оп получит 20 баллов, за вторую 10 баллов, что в сумме дает требуемые 30 баллов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
30 5 20 20 3 5
|
YES
|
|
2
|
10 4 100 5 5 1
|
NO
|