Problem:

カードはおやつに入りますか？(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



Sample input:
5 9
8 6 9 1 2


Sample output:
2

Submission status: Accepted

Solution code:
from itertools import *
from bisect import *
from math import *
from collections import *
from heapq import *
from random import *
from decimal import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def MF(): return map(float, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LF(): return list(map(float, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    n,k=MI()
    aa=LI()
    bek=[False]*(1<<n)
    for bit in range(1<<n):
        if bek[bit]==False:
            s=sum(a for i,a in enumerate(aa) if bit>>i&1)
            if s==k:bek[bit]=True
            else:continue
        for j in range(n):
            bek[bit|1<<j]=True
    mx=0
    for bit in range(1<<n):
        if bek[bit]:continue
        popcnt=bin(bit).count("1")
        if popcnt>mx:mx=popcnt
    print(n-mx)

main()