Заработай себе металлолома
(Время: 1 сек. Память: 32 Мб Сложность: 23%)
В одной замечательной игре «Рис» основной валютой является металлолом. Заработать его можно по разному, но профессиональный игрок Вася придумал оригинальный способ.
После недавнего патча Вася заметил, что одна из мини-игр стала потенциально уязвимой с точки зрения лёгкого заработка.
Мини-игра заключалась в следующем: пусть у игрока изначально имеется металлолом в количестве k. В игре есть круглый барабан, разбитый на n равных секторов и имеющий единственную стрелочку. i-й сектор содержит целое положительное число xi. Числа могут повторяться. Перед вращением барабана игрок делает ставку: сопоставляет некоторым xi какое-то целое положительное количество металлолома bj, причём сумма всех bj не может превосходить k. Заметим, что ставка делается на число, то есть если у нас несколько секторов помечены одним и тем же числом, то ставка всё равно делается один раз.
После того, как ставка была сделана, вращается барабан. Число, на котором после вращения барабана остановится стрелочка, считается выигрышным. Игрок получает в качестве выигрыша количество металлолома, равное произведению выигрышного числа на соответствующее значение bj. Ставки на остальные поля «сгорают». В частности, если игрок ничего не сопоставил выигрышному числу, то он теряет весь поставленный металлолом.
Помогите Васе определить, можно ли поставить весь свой металлолом в количестве k штук так, чтобы после игры гарантированно получить больше металлолома, чем у него было изначально.
Входные данные
В первой строке входного файла INPUT.TXT через пробел записаны два целых числа n и k – количество секций барабана и изначальное кол-во металлолома у Васи, соответственно (1 ≤ n ≤ 105, 1 ≤ k ≤ 109).
Во второй строке через пробел записаны n целых чисел xi – числа, записанные на секторах барабана (1 ≤ xi ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите в качестве ответа на поставленный вопрос одну строку: «YES», если Вася может сделать ставку так, чтобы гарантированно увеличить количество металлолома, либо «NO» в противном случае.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 12
2 2 4 4 4 | YES |
| 2 | 5 12
2 2 4 4 5 | NO |
| 3 | 3 100
2 3 4 | NO |
Пояснение
В первом тесте Вася может сопоставить 7 металлолома числу 2 , а числу 4 он может сопоставить 5 металлолома. При выигрышном числе 2 Вася получит 14 металлолома, а при выигрышном числе 4 он получит 20 металлолома. Так он в любом случае увеличит свое количество металлолома 12.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
