CF1282C Petya and Exam

Petya 参加了数学考试，他希望尽可能多地解答题目。他已经准备好并仔细研究了考试的规则。 考试共有 $n$ 道题目，需要在 $T$ 分钟内完成。因此，考试从时间 $0$ 开始，到时间 $T$ 结束。Petya 可以在 $0$ 到 $T$（包含）之间的任意整数时间离开考场。 所有题目分为两类： - 简单题——Petya 解答任意一道简单题都需要恰好 $a$ 分钟； - 困难题——Petya 解答任意一道困难题都需要恰好 $b$ 分钟（$b > a$）。 因此，如果 Petya 在时间 $x$ 开始解答一道简单题，那么他将在时间 $x+a$ 完成这道题。同理，如果他在时间 $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 \cdot 10^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 \cdot 10^5$。

输出 $m$ 行答案。每行输出一个整数，表示每个测试用例中 Petya 在离开考场前最多能获得的分数。

由 ChatGPT 4.1 翻译