Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Заработай себе металлолома

(Время: 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.TXTOUTPUT.TXT
15 12
2 2 4 4 4
YES
25 12
2 2 4 4 5
NO
33 100
2 3 4
NO

Пояснение

В первом тесте Вася может сопоставить 7 металлолома числу 2 , а числу 4 он может сопоставить 5 металлолома. При выигрышном числе 2 Вася получит 14 металлолома, а при выигрышном числе 4 он получит 20 металлолома. Так он в любом случае увеличит свое количество металлолома 12.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2021 / 2022
 2022 / 2023
 A. Вы все уже победители
 B. Заработай себе металлолома
 C. Обледенение
 D. Дата сайнс
 E. Вирусные воспоминания
 F. Докраска забора
 G. Скатерть
 H. История одного анекдота
 I. Кружок
 J. JuryGPT

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ICQ: 151483, E-mail: admin@acmp.ru



Домен viggi.ru: купить в магазине доменных имен Рег.ру