说明

作为一家现代创业公司的创始人，你们启动了一个生成式 AI 项目。图像、文本等的生成过程被拆分为 $N$ 个任务，每个任务需要恰好一台 GPU（显卡）运行一秒钟。你预先知道每个任务何时可用——任务 $i$ 在第 $T_i$ 秒变为可执行状态。你可以使用一台拥有 $M$ 块 GPU 的外部超级计算机，但每块 GPU 的使用成本不同：第 $j$ 块 GPU 每秒花费 $C_j$。你需要为每个任务 $i$ 分配一块特定的 GPU $j$ 和一个具体的时间点，使得该时间点不早于 $T_i$，且在同一时刻、同一块 GPU 上没有其他任务被调度。换言之，每块 GPU 在任意给定秒内最多只能处理一个任务。

设最终完成时间为 $F$（即所有任务中最晚的调度时间加一），总支付金额为 $S$。若任务 $i$ 被分配给 GPU $G_i$，则 $S = C_{G_1} + C_{G_2} + \dots + C_{G_N}$。你的目标是找到 $F \times S$ 的最小可能值。你需要独立解决 $Q$ 个该问题的实例。

交互说明

本题为交互式题目。你无需从标准输入读取数据或向标准输出写入数据，只需实现一个名为 solveGpus 的函数，其定义如下：

__int128 solveGpus(
    std::vector<int>& gpuCosts,
    std::vector<int>& reqTimes
);

该函数接收两个 vector 作为参数，这两个 vector 均按非递减顺序排序。你可以修改传入的 vector。函数返回类型为 __int128，表示一个 128 位整数——这是必要的，因为答案可能超出 long long 的范围。该函数会被多次调用，每次调用对应一道独立的题目实例。

你的代码中不应包含 main 函数，但可以包含任意其他辅助函数、类、变量等。你的代码必须包含头文件 gpus.h，其中为了方便你使用，已定义了用于输出 __int128 类型值的运算符。请通过以下预处理指令包含该头文件：

#include "gpus.h"

你的代码将与评测器一起编译，评测器负责读取输入并写入输出。在评测系统中，唯一计入时间限制的是你的代码实际执行所花费的时间，即输入/输出操作的时间不计入总耗时。

为便于本地测试，我们提供了本地评测器 Lgrader.cpp 以及头文件 gpus.h 的副本。你需要将自己的代码与本地评测器一同编译，以便进行测试。你可以将它们放在同一目录下，并使用以下命令：

g++ -O2 -std=c++17 -Wl,--stack,1073741824 -Wall gpus.cpp Lgrader.cpp -o gpus.exe

输入格式

本地评测器的输入格式如下：

首先为 $Q$，随后对于每个测试用例：$N, M$，接着是所有 $C_j$ 和所有 $T_i$。

1
8 4
1 2 2 6
0 0 0 0 1 2 2 2

39

提示

子任务

只有当成功通过某子任务所对应的所有测试点时，才能获得该子任务的分数。

限制条件

• $1 \le N \le 10^7$
• $1 \le M \le N$
• $0 \le T_i \le N$
• $1 \le C_i \le 2N$
• $1 \le Q \le 5$

翻译由 Qwen3.5-397B-A17B 完成