P14198 [ICPC 2024 Hangzhou R] Let's Go! New Adventure

在 Pigeland，“Pishin” 是一款热门的开放世界动作角色扮演游戏，玩家可以操控多个角色。每个角色都有独立的冒险等级（adventure rank），等级会随着该角色获得的经验值（EXP）升高。 一开始，每个角色的冒险等级都是 $0$，最高可以升到 $m$ 级。要从 $(i-1)$ 级升到 $i$ 级（$1 \leq i \leq m$），需要获得 $b_i$ 点经验。随着等级提高，升级所需经验会越来越多，即 $b_i \leq b_{i+1}$ 对于所有 $i$ 总是成立（$1 \leq i < m$）。 Grammy 计划在接下来的 $n$ 天里玩 “Pishin”。她很有钱，因此她的账号里有无限多个角色。不过因为她很懒，账号中的所有角色在这 $n$ 天的开头都是冒险等级 $0$。每天，Grammy 恰好选择一个角色来游玩，一旦她停止操控某个角色，在之后的日子里便无法再使用该角色。换句话说，每个角色只能被连续地游玩若干天。 在第 $i$ 天，Grammy 为所操控的角色获得 $a_i$ 点经验。如果她在第 $l$ 天到第 $r$ 天（包含两端）连续操控同一个角色，则该角色一共获得了 $\sum\limits_{i=l}^r a_i$ 点经验，并可升级到等级 $k$，其中 $k$ 满足 $0 \leq k \leq m$，且 $\sum\limits_{i=1}^k b_i \leq \sum\limits_{i=l}^r a_i$，且 $k$ 尽可能大。 Grammy 很贪心，希望她账号中所有角色获得的冒险等级之和最大。然而她也不想用太多不同的角色。为了平衡，她引入了一个惩罚因子 $c$。她的目标是使所有角色的冒险等级之和减去 $c \times d$ 最大，其中 $d$ 表示她使用过的不同角色数量。作为 Grammy 最好的朋友，你需要帮她计算在最优策略下她能获得的最大价值。

有多组测试数据。第一行为一个整数 $T$（$1 \leq T \leq 5 \times 10^4$），表示测试数据组数。对于每组测试数据： 第一行包含三个整数 $n,m,c$（$1 \leq n,m \leq 5 \times 10^5$，$0 \leq c \leq 5 \times 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$0 \leq a_i \leq 10^{12}$，$0 \le \sum\limits_{i = 1}^n a_i \leq 10^{12}$）。 第三行包含 $m$ 个整数 $b_1, b_2, \cdots, b_m$（$0 \leq b_i \leq 10^{12}$，$b_i \leq b_{i+1}$，$0 \leq \sum\limits_{i=1}^m b_i \leq 10^{12}$）。 保证所有测试数据中 $n$ 的总和以及 $m$ 的总和不超过 $5 \times 10^5$。

对于每组测试数据，输出一行一个整数，表示最大值。

对于第一组样例，一个方案是前 $3$ 天操控同一个角色可获得冒险等级 $4$，接下来的 $2$ 天再用另一个角色获得等级 $3$，最终价值为 $(4-2)+(3-2)=3$。 对于第二组样例，可以每天使用不同的角色，获得冒险等级分别为 $2,3,3,2$，因此价值为 $(2-1)+(3-1)+(3-1)+(2-1)=6$。 由 ChatGPT 5 翻译