在 Pigeland 中，Pishin 是一款流行的开放世界动作角色扮演游戏，用户可以扮演多个角色。每个角色都有一个独立的冒险等级，该等级会随着角色在游戏过程中获得的经验值（EXP）而提升。最初，每个角色的冒险等级均为 0 级，最高可升至 $m$ 级。要从等级 $(i - 1)$ 提升至等级 $i$ ($1 \le i \le m$)，角色需要获得 $b_i$ 点经验值。当前等级越高，升级就越困难，即对于所有 $1$ 到 $m$ 之间的 $i$，始终满足 $b_i \le b_{i+1}$。

Grammy 计划在接下来的 $n$ 天内游玩 Pishin。作为一个富家千金，她的 Pishin 账号拥有无限数量的角色。然而，由于她比较懒，她账号里的所有角色在 $n$ 天开始时冒险等级均为 0。每天，Grammy 会选择恰好一个角色进行游戏，但一旦她停止使用某个角色，她就不能在未来的任何一天继续使用该角色。换句话说，她只能在连续的日子里使用同一个角色。

在第 $i$ 天，Grammy 为她所玩的角色获得 $a_i$ 点经验值。这意味着，如果她从第 $l$ 天到第 $r$ 天（包含首尾）连续使用一个角色，该角色的冒险等级将提升至 $k$ 级，其中 $k$ 是 $0$ 到 $m$ 之间满足总获得经验值（即 $\sum_{i=l}^{r} a_i$）大于或等于升级至 $k$ 级所需经验值（即 $\sum_{i=1}^{k} b_i$）的最大整数。

作为一个贪婪的女孩，Grammy 希望最大化 $n$ 天后她所有角色的冒险等级总和。然而，作为一个专一的女孩，她不想玩太多不同的角色。为了平衡这一点，她引入了一个惩罚因子 $c$。她的目标是最大化 $n$ 天后所有角色的冒险等级总和减去 $c \times d$，其中 $d$ 是她所玩的角色总数。作为 Grammy 最好的朋友，你的任务是计算她在最优角色选择策略下能达到的最大值。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 5 \times 10^4$)，表示测试数据组数。对于每组测试数据：

第一行包含三个整数 $n, m$ 和 $c$ ($1 \le n, m \le 5 \times 10^5, 0 \le c \le 5 \times 10^5$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{12}, 0 \le \sum_{i=1}^{n} a_i \le 10^{12}$)。

第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ ($0 \le b_i \le 10^{12}, b_i \le b_{i+1}, 0 \le \sum_{i=1}^{m} b_i \le 10^{12}$)。

保证所有测试数据的 $n$ 之和与 $m$ 之和均不超过 $5 \times 10^5$。

输出格式

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

样例

样例输入 1

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

样例输出 1

3
6

说明

对于第一个样例测试数据，一种方案是使用前三天获得一个冒险等级为 4 的角色，接下来的两天获得另一个冒险等级为 3 的角色。这给出的值为 $(4 - 2) + (3 - 2) = 3$。

对于第二个样例测试数据，我们可以每天玩一个不同的角色；这分别给出了冒险等级 2, 3, 3 和 2。因此该值为 $(2 - 1) + (3 - 1) + (3 - 1) + (2 - 1) = 6$。