시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 1 | 0 | 0 | 0.000% |
Для подготовки заключительного этапа Russian Code Cup организаторам потребовалось отправить на место проведения n предметов. Для каждого предмета известна его масса в граммах mi.
Для отправки решено было воспользоваться почтовой службой «Суперэкспресс». Служба принимает к пересылке бандероли, в каждой из которых может пересылаться один или несколько предметов. При этом масса бандероли равна сумме масс пересылаемых в ней предметов.
Пересылка бандероли стоит 1 рубль за грамм, за исключением бандеролей, которые попадают под действие специального предложения. А именно, если бандероль весит ровно один килограмм, то стоимость ее пересылки составляет P рублей.
Организаторы Russian Code Cup хотят переслать все предметы, затратив минимальную возможную сумму денег. Помогите им распределить предметы по бандеролям, чтобы добиться этого.
Первая строка содержит два целых числа: n и P (1 ≤ n ≤ 14; 1 ≤ P ≤ 1000) — количество предметов и стоимость пересылки бандероли в рамках специального предложения. Вторая строка содержит n целых чисел: m1, m2, ..., mn (1 ≤ mi ≤ 1000 для всех i от 1 до n).
Выведите одно число — минимальную суммарную стоимость пересылки всех предметов в рублях.
5 800 100 200 300 400 500
1300