カードはおやつに入りますか？(Are Cards Snacks?)

square1001君は $N$ 枚のカードを持っています。

これらのカードにはそれぞれ整数が書かれており、$i$ 枚目のカードに書かれている整数は $A_i$ です。

square1001君の今日の乱数は $K$ です。square1001君はこれらの $N$ 枚のカードの中から何枚かのカードを選び、合計が $K$ となるようにしたいです。

この様子を見ていたE869120君は、これを阻止したいと考えました。

具体的には、事前に何枚かのカードを食べることで、square1001 君がどのように残りのカードを選んでも合計が $K$ とならないようにしたいです。

しかし、E869120 君は満腹であるため、なるべくカードを食べたくありません。

さて、E869120 君は最低何枚のカードを食べることでこれを阻止できますか？

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$
$A_1$ $A_2$ $A_3$ $\cdots$ $A_N$

出力

E869120 君が目的を達成するために食べるカードの枚数の最小値を、1 行で出力しなさい。

ただし、最後には改行を入れること。

制約

• $1 \leq N \leq 20$
• $1 \leq K \leq 1000000000 \ (= 10^9)$
• $0 \leq A_i \leq 1000000 \ (= 10^6)$
• 入力は全て整数である。

入力例1

5 9
8 6 9 1 2

出力例1

2

例えば、3 番目のカード (9 が書かれている) と 4 番目のカード (1 が書かれている) を食べることで、square1001 君の目的を阻止することができます。

入力例2

8 2
1 1 1 1 1 1 1 1

出力例2

7

入力例3

20 200
31 12 21 17 19 29 25 40 5 8 32 1 27 20 31 13 35 1 8 5

出力例3

6