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.

Input

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$).

Output

Print the minimum total cost of delivery of all items in rubles.

Examples