#P18269. Let's Go! New Adventure

Let's Go! New Adventure

Let's Go! New Adventure

题目描述

在 Pigeland,Pishin 是一款流行的开放世界动作角色扮演游戏。玩家可以使用多个角色,每个角色都有独立的冒险等级。角色初始等级为 00,最高等级为 mm。

从等级 i−1i-1 升到等级 ii 需要获得 bib_i 点经验。升级越来越困难,因此 bi≤bi+1b_i\le b_{i+1}。升级所需经验可以为零。

Grammy 计划接下来玩 nn 天。她有无限多个角色,但这些角色在这 nn 天开始时的等级都是 00。每天她必须恰好选择一个角色游玩。一个角色一旦停止使用,以后的任何一天都不能再使用,因此同一个角色只能在连续若干天内使用。

第 ii 天,所使用的角色会获得 aia_i 点经验。如果某个角色在第 ll 天到第 rr 天连续使用,其最终等级为满足

∑i=1kbi≤∑i=lrai\sum_{i=1}^{k}b_i\le\sum_{i=l}^{r}a_i

的最大整数 kk,其中 0≤k≤m0\le k\le m。即使这一段获得的经验为零,也按这个公式计入免费升级的等级。

她希望所有角色最终冒险等级的总和尽可能大,同时又不想使用太多不同角色。给定罚分系数 cc,设她使用的不同角色数为 dd,求

所有角色最终等级之和−c d\text{所有角色最终等级之和}-c\,d

的最大值。所有 nn 天都要安排角色,因此 d≥1d\ge1,答案可能为负。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例包含三行:

  • 第一行三个整数 n,m,cn,m,c。
  • 第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。
  • 第三行 mm 个整数 b1,…,bmb_1,\ldots,b_m,按非递减顺序给出。

输出格式

每个测试用例输出一行一个整数,表示最大目标值。答案不取模,应使用 64 位有符号整数保存。

数据范围

  • 1≤T≤5×1041\le T\le5\times10^4。
  • 1≤n,m≤5×1051\le n,m\le5\times10^5,0≤c≤5×1050\le c\le5\times10^5。
  • 0≤ai≤10120\le a_i\le10^{12},每个测试用例的 ∑ai≤1012\sum a_i\le10^{12}。
  • 0≤bi≤10120\le b_i\le10^{12},bi≤bi+1b_i\le b_{i+1},每个测试用例的 ∑bi≤1012\sum b_i\le10^{12}。
  • 每个输入文件中,所有测试用例的 nn 之和、mm 之和分别不超过 5×1055\times10^5。

样例

2
5 4 2
1 0 3 1 2
0 1 1 2
4 5 1
7 16 23 4
1 3 6 20 20
3
6

样例说明

第一个测试用例中,可以前三天使用同一个角色,升到等级 44;后两天使用另一个角色,升到等级 33。目标值为 (4−2)+(3−2)=3(4-2)+(3-2)=3。

第二个测试用例中,每天使用一个新角色,最终等级分别为 2,3,3,22,3,3,2,目标值为 (2−1)+(3−1)+(3−1)+(2−1)=6(2-1)+(3-1)+(3-1)+(2-1)=6。