← 返回题目列表

AtCoder · awc0049_d

D. 纪念品组合

中文机器翻译题面 查看原题

分数: 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