← 返回题目列表

Codeforces · 1282/C

C. Petya 和考试

中文机器翻译题面 查看原题

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