eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Почтовое отправление

Почтовое отправление

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Для подготовки заключительного этапа Russian Code Cup организаторам потребовалось отправить на место проведения n предметов. Для каждого предмета известна его масса в граммах m_i.

Для отправки решено было воспользоваться почтовой службой "Суперэкспресс". Служба принимает к пересылке бандероли, в каждой из которых может пересылаться один или несколько предметов. При этом масса бандероли равна сумме масс пересылаемых в ней предметов.

Пересылка бандероли стоит 1 рубль за грамм, за исключением бандеролей, которые попадают под действие специального предложения. А именно, если бандероль весит ровно один килограмм, то стоимость ее пересылки составляет p рублей.

Организаторы Russian Code Cup хотят переслать все предметы, затратив минимальную возможную сумму денег. Помогите им распределить предметы по бандеролям, чтобы добиться этого.

Входные данные

Первая строка содержит два целых числа: n и p~(1 \le n \le 14, 1 \le p \le 1000) — количество предметов и стоимость пересылки бандероли в рамках специального предложения. Вторая строка содержит n целых чисел: m_1, m_2, ..., m_n~(1 \le m_i \le 1000 для всех i от 1 до n).

Выходные данные

Выведите одно число — минимальную суммарную стоимость пересылки всех предметов в рублях.

Пример

Входные данные #1
5 800
100 200 300 400 500
Выходные данные #1
1300
Входные данные #2
5 800
400 400 400 400 400
Выходные данные #2
2000
Источник Russian-Code-Cup-2011 3-й кв. раунд