Postal Shipment
InterviewTime limit2sMemory limit256 MB
Split up to 14 items into parcels so that each parcel costs its total weight in rubles, except parcels of exactly 1000 grams which cost P, and minimize the total.
- Level
Medium5 of 10
- Topics
- Dynamic programming, Bit manipulation, Brute force, Combinatorics
- Solved
- No attempts yet
Problem
To prepare the final round of the Russian Code Cup, the organizers needed to send n items to the venue. The mass of each item in grams is known: mi.
They decided to use the postal service "Суперэкспресс" for the shipment. The service accepts parcels, and each parcel may contain one or more items. The mass of a parcel is the sum of the masses of the items inside it.
Shipping a parcel costs 1 ruble per gram, except for parcels that qualify for a special offer. Specifically, if a parcel weighs exactly one kilogram, its shipping cost is P rubles.
The Russian Code Cup organizers want to send all the items while spending the smallest possible amount of money. Help them distribute the items among parcels to achieve this.
Input
The first line contains two integers: n and P (1 ≤ n ≤ 14, 1 ≤ P ≤ 1000), the number of items and the shipping cost of a parcel under the special offer. The second line contains n integers: m1, m2, ..., mn (1 ≤ mi ≤ 1000 for every i from 1 to n).
Output
Print a single number: the minimum total cost of shipping all the items, in rubles.