B - フルーツの詰め合わせ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は果物屋で働いています。店には N 個のフルーツが並んでおり、i 番目のフルーツの甘さは A_i です。

そこに、青木君が仕入れ先から M 個の新しいフルーツを届けてきました。j 番目の新しいフルーツの甘さは B_j です。

高橋君は、これら合計 N + M 個のフルーツの中から、甘さの大きい順に K 個を選び、ギフト用の詰め合わせを作ることにしました。

選ばれた K 個のフルーツの甘さの合計を求めてください。

なお、甘さが等しいフルーツが複数ある場合でも、どの K 個を選んでも甘さの合計は同じ値になります。

制約

  • 1 \leq N, M
  • N + M \leq 150000
  • 1 \leq K \leq N + M
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 0 \leq B_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数である

入力

入力は以下の形式で与えられる。

N M K
A_1
A_2
\vdots
A_N
B_1
B_2
\vdots
B_M
  • 1 行目には、店にあるフルーツの個数 N、新しく届いたフルーツの個数 M、選ぶフルーツの個数 K がスペース区切りで与えられる。
  • 続く N 行のうち i 行目 (1 \leq i \leq N) には、店にある i 番目のフルーツの甘さ A_i が与えられる。
  • 続く M 行のうち j 行目 (1 \leq j \leq M) には、新しく届いた j 番目のフルーツの甘さ B_j が与えられる。

出力

選ばれた K 個のフルーツの甘さの合計を 1 行で出力せよ。

入力例 1

3 2 3
4
1
7
5
2

出力例 1

16

入力例 2

2 3 4
5
5
5
1
0

出力例 2

16

入力例 3

7 6 8
12
3
25
8
17
6
14
9
30
2
17
11
20

出力例 3

146

入力例 4

12 10 15
100
250
400
50
600
700
150
350
800
450
550
650
500
300
900
200
1000
750
125
875
425
575

出力例 4

9525

入力例 5

1 1 2
0
1000000000

出力例 5

1000000000

Score : 300 pts

Problem Statement

Takahashi works at a fruit shop. There are N fruits displayed in the shop, and the sweetness of the i-th fruit is A_i.

Then, Aoki delivers M new fruits from the supplier. The sweetness of the j-th new fruit is B_j.

Takahashi decides to select K fruits from among these N + M fruits in descending order of sweetness to make a gift assortment.

Find the total sweetness of the K selected fruits.

Note that even if there are multiple fruits with the same sweetness, the total sweetness will be the same regardless of which K fruits are chosen.

Constraints

  • 1 \leq N, M
  • N + M \leq 150000
  • 1 \leq K \leq N + M
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 0 \leq B_j \leq 10^9 (1 \leq j \leq M)
  • All input values are integers

Input

The input is given in the following format.

N M K
A_1
A_2
\vdots
A_N
B_1
B_2
\vdots
B_M
  • The first line contains the number of fruits in the shop N, the number of newly delivered fruits M, and the number of fruits to select K, separated by spaces.
  • The following N lines, where the i-th line (1 \leq i \leq N) contains the sweetness A_i of the i-th fruit in the shop.
  • The following M lines, where the j-th line (1 \leq j \leq M) contains the sweetness B_j of the j-th newly delivered fruit.

Output

Print the total sweetness of the K selected fruits on a single line.

Sample Input 1

3 2 3
4
1
7
5
2

Sample Output 1

16

Sample Input 2

2 3 4
5
5
5
1
0

Sample Output 2

16

Sample Input 3

7 6 8
12
3
25
8
17
6
14
9
30
2
17
11
20

Sample Output 3

146

Sample Input 4

12 10 15
100
250
400
50
600
700
150
350
800
450
550
650
500
300
900
200
1000
750
125
875
425
575

Sample Output 4

9525

Sample Input 5

1 1 2
0
1000000000

Sample Output 5

1000000000