Поштове відправлення#2509
Для підготовки до фінального етапу European Code Challenge організаторам необхідно відправити предметів на місце проведення заходу. Маса кожного предмета в грамах позначається як m_i.
Вони вирішили скористатися послугами поштової служби «Суперекспрес». Ця служба приймає посилки, кожна з яких може містити один або кілька предметів. Маса посилки дорівнює сумі мас всіх предметів, поміщених всередину неї.
Вартість відправки посилки становить євро за грам, за винятком посилок, що підпадають під спеціальну акцію: якщо посилка важить рівно один кілограм, вартість відправки такої посилки становить євро.
Організатори хочуть відправити всі предмети, витративши якомога менше грошей. Допоможіть їм розподілити предмети по посилках так, щоб сумарні витрати на відправку були мінімальними.
Перша рядок містить два цілих числа і p~(1 \le n \le 14, 1 \le p \le 1000) — кількість предметів і спеціальна ціна за відправку посилки.
Друга рядок містить цілих чисел m_1, m_2, \ldots, m_n~(1 \le m_i \le 1000 для всіх від до ).
Виведіть одне число — мінімально можливу сумарну вартість відправки всіх предметів (в євро).
Приклад 1
Приклад 2