AT_discovery_2016_qual_d DDPC特別ビュッフェ

A 君和 B 君正在享受 DISCO presents 发现频道编程大赛 2016 决赛的 DDPC 特别自助餐。A 君的托盘上有 $N$ 道菜，B 君的托盘上有 $M$ 道菜。A 君托盘上第 $i$ 道菜的美味度为 $A_i$，B 君托盘上第 $j$ 道菜的美味度为 $B_j$。 这两位非常要好的朋友为了让午餐更加愉快，决定恰好进行 $K$ 次操作，每次操作是将 A 君托盘上的一道菜与 B 君托盘上的一道菜交换。A 君托盘上所有菜的美味度总和为 $a$，B 君托盘上所有菜的美味度总和为 $b$，两人的幸福度定义为 $a \times b$。 请你求出经过 $K$ 次交换操作后，两人可能获得的最大幸福度。

输入以如下格式从标准输入中给出。 > $N$ $M$ $K$ > $A_1$ $A_2$ … $A_N$ > $B_1$ $B_2$ … $B_M$ - 第 1 行包含三个整数 $N,\ M\ (1 \leq N, M \leq 55)$，表示 A 君和 B 君各自拥有的菜品数量，以及交换的次数 $K\ (1 \leq K \leq 999)$。 - 第 2 行包含 $N$ 个整数 $A_i\ (0 \leq A_i \leq 22,\!222)$，表示 A 君托盘上第 $i$ 道菜的美味度。 - 第 3 行包含 $M$ 个整数 $B_j\ (0 \leq B_j \leq 22,\!222)$，表示 B 君托盘上第 $j$ 道菜的美味度。

请输出两人可能获得的最大幸福度，输出一行，末尾需换行。

## 部分分 本题设有部分分。 - 对于 $K=1$ 的数据集，答对可得 $10$ 分。 - 对于 $0 \leq A_i, B_j \leq 55$ 的数据集，答对可再得 $20$ 分。 - 对于无额外限制的数据集，答对可再得 $70$ 分，满分共 $100$ 分。 ## 样例解释 1 - 用 A 君托盘上美味度为 $3$ 的菜与 B 君托盘上美味度为 $2$ 的菜交换后，两人的幸福度为 $36$，这是最大幸福度。 ## 样例解释 2 - 第一次交换用 A 君托盘上美味度为 $2$ 的菜与 B 君托盘上美味度为 $3$ 的菜交换，第二次交换用 A 君托盘上美味度为 $3$ 的菜与 B 君托盘上美味度为 $2$ 的菜交换后，两人的幸福度为 $36$，这是最大幸福度。 由 ChatGPT 4.1 翻译