CF1282C.Petya and Exam

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 \gt 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.

佩佳参加了数学考试，希望尽可能多地解出题目。他做了充分准备，并仔细研究了考试的规则。

考试共有 $n$ 道题目，总时长为 $T$ 分钟。考试从时刻 $0$ 开始，到时刻 $T$ 结束。佩佳可以在任意整数时刻 $s$（$0 \le s \le T$）离开考场。

所有题目分为两类：

• 简单题——佩佳解任意一道简单题恰好需要 $a$ 分钟；
• 困难题——佩佳解任意一道困难题恰好需要 $b$ 分钟（$b > a$）。

因此，若佩佳在时刻 $x$ 开始解一道简单题，则该题将在时刻 $x+a$ 解出；类似地，若他在时刻 $x$ 开始解一道困难题，则该题将在时刻 $x+b$ 解出。

对于每道题，佩佳都知道它是简单题还是困难题。此外，每道题还指定一个时间 $t_i$（$0 \le t_i \le T$），表示该题在时刻 $t_i$ 起变为必答题（即强制要求）。若佩佳在时刻 $s$ 离开考场，且存在某道题 $i$ 满足 $t_i \le s$ 但佩佳并未解出它，则他本次考试得分为 $0$。否则（即他对所有满足 $t_i \le s$ 的题目均已完成求解），他的得分等于其已解出的题目总数。注意：当佩佳在时刻 $s$ 离开时，他可能既解出了“必答题”，也解出了“非必答题”。

例如，若 $n=2$，$T=5$，$a=2$，$b=3$，第一题为困难题且 $t_1=3$，第二题为简单题且 $t_2=2$。则：

• 若他在时刻 $s=0$ 离开，则得分为 $0$，因为他没有时间解出任何题目；
• 若他在时刻 $s=1$ 离开，则得分为 $0$，因为他没有时间解出任何题目；
• 若他在时刻 $s=2$ 离开，则他可通过解出第 $2$ 题获得 $1$ 分（该题必须在 $[0, 2]$ 时间段内完成）；
• 若他在时刻 $s=3$ 离开，则得分为 $0$，因为此时两道题均为必答题，但他无法在 $3$ 分钟内全部解出；
• 若他在时刻 $s=4$ 离开，则得分为 $0$，因为此时两道题均为必答题，但他仍无法在 $4$ 分钟内全部解出；
• 若他在时刻 $s=5$ 离开，则他可通过解出全部两道题获得 $2$ 分。

因此，本测试用例的答案为 $2$。

请帮助佩佳确定他在离开考试前所能获得的最高得分。

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 \lt 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$.

第一行包含一个整数 $m$（$1 \le m \le 10^4$）—— 表示测试用例的数量。

接下来的若干行描述了 $m$ 个测试用例。

每个测试用例的第一行包含四个整数 $n, T, a, b$（$2 \le n \le 2\cdot10^5$，$1 \le T \le 10^9$，$1 \le a \lt b \le 10^9$）—— 分别表示题目数量、考试总时长（单位：分钟）、解决一道简单题和一道难题所需的时间。

每个测试用例的第二行包含 $n$ 个数字（$0$ 或 $1$），以单个空格分隔：第 $i$ 个数字表示第 $i$ 道题的类型。值为 $0$ 表示该题为简单题，值为 $1$ 表示该题为难题。

每个测试用例的第三行包含 $n$ 个整数 $t_i$（$0 \le t_i \le T$），其中第 $i$ 个数表示第 $i$ 道题变为必答题的时间点。

保证所有测试用例的 $n$ 值之和不超过 $2\cdot10^5$。

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.

输出 $m$ 个测试用例的答案。对于每组数据，输出一个整数——他在离开考试前能够获得的最高分数。