Поштове відправлення

Для підготовки заключного етапу Russian Code Cup організаторам знадобилося відправити на місце проведення $n$ предметів. Для кожного предмету відома його вага в грамах $m_i$.

Для відправки вирішено було скористатися поштовою службою "Суперекспрес". Служба приймає до пересилання бандеролі, у кожній з яких може пересилатися один або декілька предметів. При цьому маса бандеролі дорівнює сумі мас предметів, які пересилаються в ній.

Пересилання бандеролі коштує $1$ рубль за грам, за винятком бандеролей, які потрапляють під дію спеціальної пропозиції. А саме, якщо бандероль важить рівно один кілограм, то вартість її пересилання складає $p$ рублів.

Організатори Russian Code Cup хочуть переслати всі предмети, витративши мінімальну можливу суму грошей. Допоможіть їм розподілити предмети на бандеролі так, щоб добитися цього.

Вхідні дані

Перший рядок містить два цілі числа: $n$ та $p(1\le n\le 14,1\le p\le 1000)$ — кількість предметів та вартість пересилання бандеролі в рамках спеціальної пропозиції. Другий рядок містить $n$ цілих чисел: $m_1,m_2,...,m_n(1\le m_i\le 1000$ для усіх $i$ від $1$ до $n$).

Вихідні дані

Виведіть одне число — мінімальну сумарну вартість пересилання усіх предметів у рублях.

Приклади