核心调度

题目描述:

现在有一块最新研发的双核心中央处理器（CPU）。这块 CPU 采用了异构设计，由一颗性能极其强劲的大核（Performance Core）和一颗主打稳定并发的小核（Efficiency Core）组成。根据官方给定的参数，大核每秒能够处理 $w$ 个单位的计算量，而小核每秒能够处理 $f$ 个单位的计算量。

在计算机启动初始化阶段，系统会产生 $n$ 个相互独立的核心初始化任务，第 $i$ 个任务的总计算量为 $s_i$。为了保证系统安全，每个任务只能被不可分割地整体分配给某一颗核心独立完成，中途不可转移。

经过技术骨干小C的深度代码分析，他发现这些任务的性质各有不同：

• 第一类任务（如高精度图像识别、复杂的神经网络推演）依赖高级指令集，必须且只能分配给大核完成。
• 第二类任务（如传感器轮询、基础硬件状态保持）为了防止抢占重要资源，必须且只能分配给小核完成。
• 第三类任务（如普通的数据压缩、日志清理）属于通用计算，既可以分配给大核，也可以分配给小核。

现在计算机即将启动，大核和小核是并行运算的（即同时开始处理各自队列中的任务）。整个计算机初始化完成的标志是所有分配出去的任务都被处理完毕。

需要特别注意的是，底层系统时钟只接受整数秒。如果你给某颗核心分配的任务算得理论耗时带有小数（例如 $1.3$ 秒），系统会将其向上取整为 $2$ 秒。两颗核心各自完成各自队列的向上取整耗时后，取两者的最大值，即为系统初始化的最短用时。

请你编写一段程序，将这 $n$ 个任务合理分配给双核 CPU，使得计算机完成系统初始化的总耗时最短。

输入格式:

第一行包含一个正整数 $T$，表示测试数据的组数。

对于每组测试数据：

第一行包含三个正整数 $n$、$w$、$f$，分别表示任务总数、大核的每秒算力、小核的每秒算力。

接下来 $n$ 行，每行包含两个非负整数 $type_i$ 和 $s_i$，使用空格隔开。

• $type_i$ 表示任务的类型限制：$type_i = 1$ 表示仅限大核，$type_i = 0$ 表示仅限小核，$type_i = 2$ 表示不限核心。
• $s_i$ 表示该任务所需的计算量。

输出格式:

输出共 $T$ 行，每行包含一个正整数，表示对于该组测试数据的最短耗时（单位：秒）。

数据范围:

设 $M = \sum_{type_i=2} s_i$，即所有不限核心的任务的计算量之和。

对于 $100\%$ 的数据，保证 $1 \le T \le 10$，$1 \le n \le 500$，$1 \le w, f \le 10^4$，$1 \le s_i \le 10^5$，且 $M \le 10^4$。

各测试点的数据范围与特殊性质梯度如下表所示：

样例输入:

2
3 5 2
1 11
0 3
2 6
5 2 2
2 6
2 6
2 4
2 4
2 4

样例输出:

4
6

提示:

• 任务 1 必须给大核，大核目前总任务量为 $11$。
• 任务 2 必须给小核，小核目前总任务量为 $3$。
• 任务 3（计算量为 $6$）不限制核心。

来源: 温州市计算机学会