Petya has come to the math exam and wants to solve as many problems as possible. He prepared and carefully studied the rules by which the exam passes.

The exam consists of $n$ problems that can be solved in $T$ minutes. Thus, the exam begins at time $0$ and ends at time $T$. Petya can leave the exam at any integer time from $0$ to $T$, inclusive.

All problems are divided into two types:   easy problems — Petya takes exactly $a$ minutes to solve any easy problem;  hard problems — Petya takes exactly $b$ minutes ($b > a$) to solve any hard problem. 

Thus, if Petya starts solving an easy problem at time $x$, then it will be solved at time $x+a$. Similarly, if at a time $x$ Petya starts to solve a hard problem, then it will be solved at time $x+b$.

For every problem, Petya knows if it is easy or hard. Also, for each problem is determined time $t_i$ ($0 \le t_i \le T$) at which it will become mandatory (required). If Petya leaves the exam at time $s$ and there is such a problem $i$ that $t_i \le s$ and he didn't solve it, then he will receive $0$ points for the whole exam. Otherwise (i.e if he has solved all such problems for which $t_i \le s$) he will receive a number of points equal to the number of solved problems. Note that leaving at time $s$ Petya can have both "mandatory" and "non-mandatory" problems solved.

For example, if $n=2$, $T=5$, $a=2$, $b=3$, the first problem is hard and $t_1=3$ and the second problem is easy and $t_2=2$. Then:  if he leaves at time $s=0$, then he will receive $0$ points since he will not have time to solve any problems;  if he leaves at time $s=1$, he will receive $0$ points since he will not have time to solve any problems;  if he leaves at time $s=2$, then he can get a $1$ point by solving the problem with the number $2$ (it must be solved in the range from $0$ to $2$);  if he leaves at time $s=3$, then he will receive $0$ points since at this moment both problems will be mandatory, but he will not be able to solve both of them;  if he leaves at time $s=4$, then he will receive $0$ points since at this moment both problems will be mandatory, but he will not be able to solve both of them;  if he leaves at time $s=5$, then he can get $2$ points by solving all problems. 

Thus, the answer to this test is $2$.

Help Petya to determine the maximal number of points that he can receive, before leaving the exam.


-----Input-----

The first line contains the integer $m$ ($1 \le m \le 10^4$) — the number of test cases in the test.

The next lines contain a description of $m$ test cases. 

The first line of each test case contains four integers $n, T, a, b$ ($2 \le n \le 2\cdot10^5$, $1 \le T \le 10^9$, $1 \le a < b \le 10^9$) — the number of problems, minutes given for the exam and the time to solve an easy and hard problem, respectively.

The second line of each test case contains $n$ numbers $0$ or $1$, separated by single space: the $i$-th number means the type of the $i$-th problem. A value of $0$ means that the problem is easy, and a value of $1$ that the problem is hard.

The third line of each test case contains $n$ integers $t_i$ ($0 \le t_i \le T$), where the $i$-th number means the time at which the $i$-th problem will become mandatory.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2\cdot10^5$.


-----Output-----

Print the answers to $m$ test cases. For each set, print a single integer — maximal number of points that he can receive, before leaving the exam.


-----Example-----
Input
10
3 5 1 3
0 0 1
2 1 4
2 5 2 3
1 0
3 2
1 20 2 4
0
16
6 20 2 5
1 1 0 1 0 0
0 8 2 9 11 6
4 16 3 6
1 0 1 1
8 3 5 6
6 20 3 6
0 1 0 0 1 0
20 11 3 20 16 17
7 17 1 6
1 1 0 1 0 0 0
1 7 0 11 10 15 10
6 17 2 6
0 0 1 0 0 1
7 6 3 7 10 12
5 17 2 5
1 1 1 1 0
17 11 10 6 4
1 1 1 2
0
1

Output
3
2
1
0
1
4
0
1
2
1

Difficulty: interview

Starter code:

Solutions:
import sys
from operator import itemgetter

def count(a, b, num_a, num_b, cur_time):
	current_result = 0
	#print('count time = ', cur_time, "num_a =", num_a, 'num_b = ', num_b)
	if num_a * a + num_b * b <= cur_time and cur_time >= 0:
		cur_time -= num_a * a + num_b * b
		current_result = num_a + num_b
		if num_a < total_a:
			if (total_a - num_a) * a <= cur_time:
				current_result += total_a - num_a
				cur_time -= (total_a - num_a) * a
				#print(1)
			else:
				current_result += cur_time // a
				cur_time -= a *(cur_time // a)
				#print(2)
		if num_b < total_b:
			if (total_b - num_b) * b <= cur_time:
				current_result += total_b - num_b
				#print(3)
			else:
				#print(4)
				current_result += cur_time // b
	#print('current_result = ', current_result)
	return current_result


def solve(n, T, a, b, tasks, total_a, total_b):	
	tasks = sorted(tasks)
	#print(tasks)
	result = 0
	num_a = 0
	num_b = 0

	for i in range(len(tasks)):
		time, t = tasks[i] 
		#print(tasks[i])
		cur_time = time - 1
		#print('cur time = ', cur_time)
		current_result = count(a, b, num_a, num_b, cur_time)
		result = max(current_result, result)

		if t == 0:
			num_a += 1
		else:
			num_b += 1

		if i == len(tasks) - 1 or tasks[i + 1][1] != tasks[i][1]:
			result = max(result, count(a, b, num_a, num_b, cur_time))

		#print("i =", i, "result = ", result)

	result = max(result, count(a, b, total_a, total_b, T))
	return result


q = int(input())

for i in range(q):
	n, T, a, b = list(map(int, input().split()))
	types = list(map(int, input().split()))
	total_a, total_b = 0, 0
	for t in types:
		if t == 0:
			total_a += 1
		else:
			total_b += 1
	t = list(map(int, input().split()))
	#print(t)
	#print(types)
	tasks = list(zip(t, types))
	print(solve(n, T, a, b, tasks, total_a, total_b))	


import sys
input = sys.stdin.readline

t=int(input())
for testcases in range(t):
    n,T,a,b=list(map(int,input().split()))
    A=list(map(int,input().split()))
    L=list(map(int,input().split()))

    LCAN=[T]

    EASY=[]
    HARD=[]

    for i in range(n):
        if A[i]==0:
            EASY.append(L[i])
        else:
            HARD.append(L[i])

        if L[i]>1:
            LCAN.append(L[i]-1)

    LCAN=sorted(set(LCAN))

    EASY.sort()
    HARD.sort()

    #print(LCAN,a,b)
    #print(EASY)
    #print(HARD)
    #print()

    eind=0
    hind=0

    LENE=len(EASY)
    LENH=len(HARD)

    needtime=0
    ANS=0
    
    for time in LCAN:
        while eind<LENE and EASY[eind]<=time:
            needtime+=a
            eind+=1

        while hind<LENH and HARD[hind]<=time:
            needtime+=b
            hind+=1

        if time<needtime:
            continue
        else:
            rest=time-needtime
            score=eind+hind

            if (LENE-eind)*a>=rest:
                score+=rest//a
            else:
                score=LENE+hind
                rest-=(LENE-eind)*a

                score+=min(LENH-hind,rest//b)

            ANS=max(ANS,score)
            
    print(ANS)
                

        

            
        

    


m = int(input())
for ii in range(m):
    n, T, a, b = list(map(int, input().split()))
    score = [a,b]
    d = list(map(int, input().split()))
    t = list(map(int, input().split()))
    easy = 0
    for d1 in d:
        if d1 == 0:
            easy += 1
    diff = list(zip(t,d))
    diff = sorted(diff) # from least to greatest
    cnt = 0
    cur = 0
    ans = 0
    for i in range(n):
        t,d = diff[i]
        # print('----',i, cur, cnt)
        if cur < t and cur <= T:
            # can leave
            ans = max(cnt, ans)
            # try easy problems as much as possible
            tmp = (t - 1 - cur) // a
            tmp = min(tmp, easy)
            ans = max(ans, cnt + tmp)

        # force this one
        cnt += 1
        cur += score[d]
        if d==0:
            easy -= 1
    if cur <= T:
        ans = max(cnt, ans)

    print(ans)


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int,minp().split()))

def solve():
	n, T, a, b = mints()
	h = list(mints())
	c = [0, 0]
	for i in h:
		c[i] += 1
	i = 0
	t = [None]*n
	for j in mints():
		t[i] = (j, i)
		i += 1
	t.sort()
	tt = 0
	tmust = 0
	cmust = 0
	r = 0
	for ii in range(len(t)):
		tn, i = t[ii]
		if tt < tn - 1:
			tt = tn - 1
			left = tt - tmust
			if left >= 0:
				ac = min(left//a, c[0])
				bc = min((left - ac*a)//b, c[1])
				#print(tt, tmust, left, cmust, ac, bc)
				r = max(r, cmust + ac + bc)
		if h[i]:
			tmust += b
			c[1] -= 1
		else:
			tmust += a
			c[0] -= 1
		#print("tmust", tmust)
		cmust += 1
	if tt < T:
		tt = T
		left = tt - tmust
		if left >= 0:
			ac = min(left//a, c[0])
			bc = min((left - ac*a)//b, c[1])
			r = max(r, cmust + ac + bc)
	return r

for i in range(mint()):
	print(solve())



m = int(input())
for i in range(m):
	n, T, a, b = list(map(int, input().split()))
	is_hard = list(map(int, input().split()))
	total_hard = sum(is_hard)
	total_easy = n - total_hard
	time_mandatory = list(map(int, input().split()))
	mandatory_times = sorted([(time_mandatory[i], i)
		for i in range(len(time_mandatory))])
	mandatory_times.append((T, -1))
	maximal_points = 0
	min_easy = 0
	min_hard = 0
	for (i, (time, problem_no)) in enumerate(mandatory_times):
		bad = False
		if i != len(mandatory_times) - 1 and mandatory_times[i + 1][0] == time:
			bad = True
		remaining_easy = total_easy - min_easy
		remaining_hard = total_hard - min_hard
		remaining_time = time - 1 - min_easy * a - min_hard * b
		if remaining_time >= 0:
			if remaining_time >= a * remaining_easy:
				maximal_points = max(maximal_points,
					min_easy + min_hard + remaining_easy +
					min((remaining_time - a * remaining_easy) // b,
						remaining_hard))
			else:
				maximal_points = max(maximal_points,
					min_easy + min_hard + remaining_time // a)
		if problem_no == -1:
			min_easy = min_easy
		elif is_hard[problem_no] == 1:
			min_hard += 1
		else:
			min_easy += 1
		if bad:
			continue
		remaining_easy = total_easy - min_easy
		remaining_hard = total_hard - min_hard
		remaining_time = time - min_easy * a - min_hard * b
		if remaining_time >= 0:
			if remaining_time >= a * remaining_easy:
				maximal_points = max(maximal_points,
					min_easy + min_hard + remaining_easy +
					min((remaining_time - a * remaining_easy) // b,
						remaining_hard))
			else:
				maximal_points = max(maximal_points,
					min_easy + min_hard + remaining_time // a)
	print(maximal_points)


t = int(input())
for _ in range(t):
    n, T, a, b = list(map(int, input().split(' ')))
    task_t = list(map(int, input().split(' ')))
    ness = list(map(int, input().split(' ')))

    perm = sorted(list(range(n)), key=lambda i: ness[i])

    score = 0
    tot_hard = sum(task_t)
    tot_easy = n - tot_hard

    must_easy = 0
    must_hard = 0
    for i in range(n):
        if i > 0 and ness[perm[i]] == ness[perm[i - 1]]:
            if task_t[perm[i]] == 0:
                must_easy += 1
            else:
                must_hard += 1
            continue

        tm = ness[perm[i]] - 1

        req_time = must_easy * a + must_hard * b

        if req_time > tm:
            if task_t[perm[i]] == 0:
                must_easy += 1
            else:
                must_hard += 1
            continue

        extra_time = tm - req_time
        extra_easy = min(extra_time // a, tot_easy - must_easy)

        extra_time -= a * extra_easy
        extra_hard = min(extra_time // b, tot_hard - must_hard)

        #print(tm, extra_easy, extra_hard, must_easy, must_hard)

        score = max(score, extra_easy + extra_hard + must_easy + must_hard)

        if task_t[perm[i]] == 0:
            must_easy += 1
        else:
            must_hard += 1

    if tot_easy * a + tot_hard * b <= T:
        score = n
    print(score)