Dhiraj loves Chocolates.He loves chocolates so much that he can eat up to $1000$ chocolates a day. But his mom is fed up by this habit of him and decides to take things in her hand.
Its diwali Season and Dhiraj has got a lot of boxes of chocolates and Dhiraj's mom is afraid that dhiraj might eat all boxes of chocolates.
So she told Dhiraj that he can eat only exactly $k$ number of chocolates and dhiraj has to finish all the chocolates in box selected by him and then move on to next box of chocolate.Now Dhiraj is confused that whether he will be able to eat $k$ number of chocolates or not. Since dhiraj is weak at maths,he asks for your help to tell him whether he can eat $k$ number of chocolates or not. 
So given number of chocolates  are $k$ which dhiraj has to eat and the boxes of chocolates each containing some number of chocolates, tell whether dhiraj will be able to eat $k$ number of chocolates or not.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- $k$, representing the number of chocolates dhiraj has to eat.
- the third line contains $N$ representing the no. of boxes of chocolates.
- fourth line contains list of $a[]$ size $N$ specifying the number of chocolates in each Box.

-----Output:-----
- For each testcase, output in a single line answer $0$ or $1$.
- $0$ if dhiraj cant eat $k$ chocolates from given combination and $1$ if he can eat $k$ chocolates from given combination.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq K \leq 10^7$
- $1 \leq  N \leq 800$
- $1 \leq a[i] \leq 10^3$

-----Sample Input:-----
2
20
5
8 7 2 10 5
11
4
6 8 2 10

-----Sample Output:-----
1
0

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def isSubsetSum(arr, n, sum):
	subset = [[False for j in range(sum + 1)] for i in range(3)]
	for i in range(n + 1):
		for j in range(sum + 1):
			if j == 0:
				subset[i % 2][j] = True
			elif i == 0:
				subset[i % 2][j] = False
			elif arr[i - 1] <= j:
				subset[i % 2][j] = subset[(i + 1) % 2][j - arr[i - 1]] or subset[(i + 1) % 2][j]
			else:
				subset[i % 2][j] = subset[(i + 1) % 2][j]
	return subset[n % 2][sum]
for _ in range(int(input())):
	(k, n, a) = (int(input()), int(input()), list(map(int, input().split())))
	if sum(a) < k or k < min(a):
		print(0)
		continue
	print(1) if isSubsetSum(a, n, k) else print(0)


def isSubsetSum(set, n, sum):
	subset = [[False for i in range(sum + 1)] for i in range(n + 1)]
	for i in range(n + 1):
		subset[i][0] = True
	for i in range(1, sum + 1):
		subset[0][i] = False
	for i in range(1, n + 1):
		for j in range(1, sum + 1):
			if j < set[i - 1]:
				subset[i][j] = subset[i - 1][j]
			if j >= set[i - 1]:
				subset[i][j] = subset[i - 1][j] or subset[i - 1][j - set[i - 1]]
	return subset[n][sum]
for _ in range(int(input())):
	K = int(input())
	N = int(input())
	array = list(map(int, input().split()))
	if K > sum(array):
		print(0)
	elif isSubsetSum(array, N, K):
		print(1)
	else:
		print(0)