Petya 来参加数学考试了,想要解决尽可能多的问题。他准备并仔细研究了考试通过的规则。
考试包含 $$$n$$$ 个问题,可在 $$$T$$$ 分钟内解决。因此,考试于时间 $$$0$$$ 开始,于时间 $$$T$$$ 结束。 Petya 可以在 $$$0$$$ 到 $$$T$$$(含)之间的任意整数时间离开考试。
所有问题分为两类:
- 简单问题 - Petya 只需 $$$a$$$ 分钟即可解决任何简单问题;
- 难题 — Petya 需要 $$$b$$$ 分钟 ($$$b > a$$$) 来解决任何难题。
因此,如果 Petya 在 $$$x$$$ 时间开始解决一个简单的问题,那么它将在 $$$x+a$$$ 时间得到解决。类似地,如果 Petya 在某个时间 $$$x$$$ 开始解决一个难题,那么它将在 $$$x+b$$$ 时间得到解决。
对于每一个问题,Petya 都知道它是简单还是困难。此外,对于每个问题都确定了时间 $$$t_i$$$ ($$$0 \le t_i \le T$$$),在该时间它将成为强制性的(必需的)。如果 Petya 在 $$$s$$$ 时间离开考试,并且存在 $$$i$$$ 导致 $$$t_i \le s$$$ 的问题并且他没有解决,那么他整个考试将获得 $$$0$$$ 分。否则(即,如果他已经解决了 $$$t_i \le s$$$ 的所有此类问题),他将获得等于已解决问题数量的分数。请注意,在 $$$s$$$ 时间离开 Petya 可以同时解决“强制”和“非强制”问题。
例如,如果$$$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$$$积分,因为此时这两个问题都是强制性的,但他将无法同时解决这两个问题;
- 如果他在 $$$s=4$$$ 时间离开,那么他将获得 $$$0$$$ 积分,因为此时这两个问题都是强制性的,但他将无法同时解决这两个问题;
- 如果他在$$$s=5$$$时间离开,那么他可以通过解决所有问题获得$$$2$$$分。
因此,该测试的答案是 $$$2$$$。
在离开考试之前,帮助 Petya 确定他可以获得的最大分数。
输入
第一行包含整数 $$$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 < 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$$$。
输出
打印 $$$m$$$ 测试用例的答案。对于每一组,打印一个整数——他在离开考试之前可以获得的最大分数。
示例
输入 #1
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
输出 #1
3 2 1 0 1 4 0 1 2 1