CF1618G Trader Problem

Monocarp 又在玩电脑游戏了！这个游戏有一种独特的交易机制。 要与某个角色进行交易，Monocarp 需要选择他拥有的某一件物品，并用它交换对方拥有的某一件物品。每件物品都有一个整数价格。如果 Monocarp 选择的物品价格为 $x$，那么他可以用它交换对方价格不超过 $x+k$ 的任意一件物品（只能交换一件）。 Monocarp 最初有 $n$ 件物品，第 $i$ 件物品的价格为 $a_i$。与 Monocarp 交易的角色有 $m$ 件物品，第 $i$ 件物品的价格为 $b_i$。Monocarp 可以和这个角色进行任意多次交易（也可以一次都不交易），每次都按照上述规则交换一件物品。注意，如果 Monocarp 在一次交换中获得了某件物品，那么他可以用这件物品继续进行交换（因为此时这件物品属于他了）；反之亦然：如果 Monocarp 用自己的某件物品交换了另一件物品，他也可以通过再次交换将原来的物品换回来。 你需要回答 $q$ 个询问。每个询问给定一个整数 $k$，询问在每次交易中都可以用价格为 $x$ 的物品交换价格不超过 $x+k$ 的物品的前提下，Monocarp 经过若干次交易后，能够拥有的物品总价格的最大值。注意，所有询问相互独立：交易实际上并不会发生，Monocarp 只是想计算他最多能获得多少总价值。

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n, m, q \le 2 \cdot 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示 Monocarp 拥有的物品价格。 第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$（$1 \le b_i \le 10^9$），表示对方角色拥有的物品价格。 第四行包含 $q$ 个整数，第 $i$ 个整数为第 $i$ 个询问的 $k$ 值（$0 \le k \le 10^9$）。

对于每个询问，输出一个整数，表示在给定 $k$ 值下，Monocarp 经过若干次交易后能够拥有的物品总价格的最大值。

由 ChatGPT 4.1 翻译