D - Souvenir Combinations Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は旅行先でお土産を選ぼうとしています。

お土産売り場には N 種類のお菓子と M 種類の飲み物が売られています。i 番目のお菓子の美味しさは A_i 、j 番目の飲み物の美味しさは B_j です。

i 番目のお菓子と j 番目の飲み物を組み合わせたときの満足度を、美味しさの積 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 または j_1 \neq j_2 であれば、たとえ満足度の値が等しくても異なる組み合わせとみなします。すなわち、上位 K 個を選ぶ際にも合計を求める際にも、それぞれ別の組み合わせとして 1 個ずつ数えます。

制約

  • 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
  • 1 行目には、お菓子の種類数 N 、飲み物の種類数 M 、選ぶ組み合わせの個数 K が、空白区切りで与えられる。
  • 2 行目には、各お菓子の美味しさ A_1, A_2, \dots, A_N が、空白区切りで与えられる。
  • 3 行目には、各飲み物の美味しさ B_1, B_2, \dots, B_M が、空白区切りで与えられる。

出力

N \times M 通りの組み合わせの満足度のうち、大きい方から K 個の合計値を整数として 1 行で出力せよ。末尾に改行を含めること。

入力例 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

Score : 400 pts

Problem Statement

Takahashi is choosing souvenirs at his travel destination.

The souvenir shop sells N types of sweets and M types of drinks. The deliciousness of the i-th sweet is A_i, and the deliciousness of the j-th drink is B_j.

The satisfaction of combining the i-th sweet and the j-th drink is defined as the product of their deliciousness values, A_i \times B_j.

There are N \times M possible combinations of sweets and drinks in total. When these N \times M combinations are sorted in descending order of satisfaction, find the sum of the first K satisfaction values.

Note that combinations (i_1, j_1) and (i_2, j_2) are considered different as long as i_1 \neq i_2 or j_1 \neq j_2, even if their satisfaction values are equal. That is, when selecting the top K and computing the sum, each combination is counted individually as a separate one.

Constraints

  • 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)
  • All input values are integers.

Input

N M K
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M
  • The first line contains the number of sweet types N, the number of drink types M, and the number of combinations to select K, separated by spaces.
  • The second line contains the deliciousness of each sweet A_1, A_2, \dots, A_N, separated by spaces.
  • The third line contains the deliciousness of each drink B_1, B_2, \dots, B_M, separated by spaces.

Output

Output the sum of the top K satisfaction values (in descending order) among all N \times M combinations, as an integer on a single line. Include a newline at the end.

Sample Input 1

2 3 3
3 1
2 4 1

Sample Output 1

22

Sample Input 2

4 4 5
5 3 7 1
4 6 2 8

Sample Output 2

196

Sample Input 3

5 6 8
10 20 30 40 50
3 6 9 12 15 18

Sample Output 3

5040