The post office#2509
To prepare for the final stage of the European Code Challenge, the organizers need to send items to the event location. Each item has a known mass in grams, denoted by m_i.
They decided to use the postal service "Superexpress" for shipping. This service accepts parcels, each of which may contain one or more items. The mass of a parcel is equal to the sum of the masses of all items placed inside it.
The cost of sending a parcel is euro per gram, except for parcels that fall under the special offer: if a parcel weighs exactly one kilogram, the shipping cost is euros.
The organizers want to send all items while spending as little money as possible. Help them distribute the items among parcels so as to minimize the total shipping cost.
The first line contains two integers and p~(1 \le n \le 14, 1 \le p \le 1000) — the number of items and the special offer price for shipping a parcel.
The second line contains integers m_1, m_2, \ldots, m_n~(1 \le m_i \le 1000 for all from to ).
Print one number — the minimum possible total cost of shipping all items (in euros).
Example 1
Example 2