分数: 400 分
问题陈述
高桥正在他的旅行目的地挑选纪念品。
纪念品商店有卖 N 糖果的类型和 M 饮料类型。的美味 i-第一个甜蜜是 A_i,以及美味 j第一杯饮料是 B_j.
的 满意 结合 i-第甜和 j-th 饮料被定义为其美味值的乘积, A_i \times B_j.
有 N \times M 糖果和饮料的可能组合。当这些 N \times M 组合按照满意度降序排列,求第一个的总和 K 满意度值。
请注意组合 (i_1, j_1) 和 (i_2, j_2) 被认为是不同的,只要 i_1 \neq i_2 or j_1 \neq j_2,即使他们的满意度值相同。也就是说,当选择顶部 K 并计算总和,每个组合都被单独计算为一个单独的组合。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq K \leq \min(N \times M,\, 2 \times 10^5)
- 1 \leq A_i \leq 10^5 (1 \leq i \leq N)
- 1 \leq B_j \leq 10^5 (1 \leq j \leq M)
- 所有输入值均为整数。
输入
N M K A_1 A_2 \dots A_N B_1 B_2 \dots B_M
- 第一行包含糖果类型的数量 N,饮料种类数量 M,以及要选择的组合数 K,用空格分隔。
- 第二行包含了每种糖果的美味 A_1, A_2, \dots, A_N,用空格分隔。
- 第三行包含每种饮料的美味 B_1, B_2, \dots, B_M,用空格分隔。
输出
输出顶部的总和 K 满意度值(按降序排列) N \times M 组合,作为单行上的整数。在末尾添加换行符。
样本输入 1
2 3 3 3 1 2 4 1
示例输出 1
22
示例输入 2
4 4 5 5 3 7 1 4 6 2 8
示例输出 2
196
示例输入 3
5 6 8 10 20 30 40 50 3 6 9 12 15 18
示例输出 3
5040