2017 历史的进程 Week 5:「一场」测验赛

G. 爱狗狗的两个 dalao

单点时限: 2.0 sec

内存限制: 256 MB

xxtt 和 ultmaster 一起养了 $n$ 个狗狗(???)。有一天,突发奇想的两人带这些狗狗去山上玩,然而爬到山顶之后大家都累了,狗狗们实在没力气往下爬了(QAQ)。

那没关系啊,反正两位都很有钱嘛。不就是搞个缆车嘛。他们听说缆车最多只能承受 $M$ 的重量。至于哪些狗狗嘛,每个听说重量在 $w_1, w_2, \ldots, w_n$ 的样子。每次用一下缆车呢,两位就要用掉一百万人民币。虽说有钱但是毕竟贵,他们还是想少花一点钱,请问他们最少要花多少钱才能把所有狗狗都搞下山呢?

他们自己?嗨呀年轻人有力气,走下去就行了~

输入格式

第一行两个整数 $n, M$ $(1 \leq n \leq 18, 1 \leq M \leq 10^9)$,表示狗狗的数量与缆车的承重量。

接下来 $n$ 行,每行一个整数,表示这些狗狗的重量 $w_1, w_2, \ldots, w_n$ $(1 \leq w_i \leq 10^9)$。

输出格式

输出仅一行,即 xxtt 和 ultmaster 两个人总共要花多少百万人民币。

样例

Input
5 2333
1998
226
1998
816
999
Output
3