Problems
The post office
The post office
For preparation to the final phase of Russian Code Cup the organisers need to send to the contest place $n$ items. The weight of each item is known and equals in grams to $m_i$.
It was decided to send the items using the service "Superexpress". The service takes forwarding parcels, each may send one or more items. The weight of each parcel equals to the total weight of items in it.
Sending parcels costs $1$ ruble per gram, except for parcels that are subject to the special offer. Namely, if the parcel weighs exactly one kilogram, the cost of its shipping is $p$ rubles.
The organisers of Russian Code Cup want to send all the items, spending the minimum amount of money. Help them to distribute the items to the parcels to achieve this.
\InputFile
The first line contains two integers: $n$ and $p~(1 \le n \le 14, 1 \le p \le 1000)$ --- the number of items and the delivery cost of a parcel using special offer. The second line contains $n$ integers: $m_1, m_2, ..., m_n~(1 \le m_i \le 1000$ for all $i$ from $1$ to $n$).
\OutputFile
Print the minimum total cost of delivery of all items in rubles.
Input example #1
5 800 100 200 300 400 500
Output example #1
1300
Input example #2
5 800 400 400 400 400 400
Output example #2
2000