Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef is playing a card game called Blackjack. He starts with a deck of $N$ cards (numbered $1$ through $N$), where for each valid $i$, the $i$-th card has an integer $A_{i}$ written on it. Then he starts dealing the cards one by one in the order from card $1$ to card $N$. Chef wins if at some moment in time, the sum of all the cards dealt so far is between $X$ and $Y$ inclusive; if this never happens, Chef loses.

We want Chef to win the game, so without him noticing, we will swap some pairs of cards (possibly none) before the game starts. Find the smallest number of swaps we need so that Chef would win the game, or determine that it is impossible to make Chef win.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains three space-separated integers $N$, $X$ and $Y$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the smallest required number of swaps or $-1$ if Chef cannot win.

------  Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ N,X,Y ≤ 10^{3}$
$X ≤ Y$
$1 ≤ A_{i} ≤ 10^{3}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{4}$

------  Subtasks ------
Subtask #1 (22 points): Chef can win if we make up to $2$ swaps

Subtask #2 (34 points):
$1 ≤ N,X,Y ≤ 400$
$1 ≤ A_{i} ≤ 400$ for each valid $i$
the sum of $N$ over all test cases does not exceed $4,000$

Subtask #3 (44 points): original constraints

----- Sample Input 1 ------ 
3

3 4 5

1 2 3

3 3 4

1 2 3

2 20 30

40 10
----- Sample Output 1 ------ 
1

0

-1
----- explanation 1 ------ 
Example case 1: We can swap the last card with one of the first two cards.

Example case 2: No swaps are necessary, Chef wins after dealing the first two cards.

Example case 3: The order of the cards in the deck does not matter, Chef cannot win.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Bit manipulation

Mathematics


Solutions:
left = [[0] * 1024 for _ in range(1024)]
right = [[0] * 1024 for _ in range(1024)]

def solveCase(N, X, Y, a):
	for i in range(N + 2):
		left[0][i] = right[0][i] = 0
	left[0][0] = 1
	right[0][N] = (1 << Y + 1) - (1 << X)
	max_mask = (1 << Y + 1) - 1
	for missed in range(N // 2 + 1):
		left[missed + 1][0] = 0
		for i in range(N):
			left[missed][i + 1] |= left[missed][i] << a[i] & max_mask
			left[missed + 1][i + 1] = left[missed][i]
		right[missed + 1][N] = 0
		for i in range(N, 0, -1):
			right[missed + 1][i - 1] = right[missed][i] >> a[i - 1]
			right[missed][i - 1] |= right[missed][i]
		if any((right[missed][i] & left[missed][i] for i in range(1, N + 1))):
			return missed
	return -1
T = int(input())
for _ in range(T):
	(N, X, Y) = map(int, input().split())
	a = list(map(int, input().split()))
	print(solveCase(N, X, Y, a))


def solveCase(N, X, Y, a):
	(left_cur, left_next) = ([0] * (N + 1), [0] * (N + 1))
	(right_cur, right_next) = ([0] * (N + 1), [0] * (N + 1))
	left_cur[0] = 1
	right_cur[N] = (2 << Y) - (1 << X)
	max_mask = (2 << Y) - 1
	for missed in range(N // 2 + 1):
		for i in range(N):
			left_cur[i + 1] |= left_cur[i] << a[i] & max_mask
			left_next[i + 1] = left_cur[i]
		for i in range(N, 0, -1):
			right_next[i - 1] = right_cur[i] >> a[i - 1]
			right_cur[i - 1] |= right_cur[i]
		if any((right_cur[i] & left_cur[i] for i in range(1, N + 1))):
			return missed
		(left_cur, left_next) = (left_next, left_cur)
		(right_cur, right_next) = (right_next, right_cur)
	return -1
T = int(input())
for _ in range(T):
	(N, X, Y) = map(int, input().split())
	a = list(map(int, input().split()))
	print(solveCase(N, X, Y, a))