分数: 300 分
问题陈述
高桥在一家水果店工作。有 N 店里陈列的水果,还有甜度 i- 第一个水果是 A_i.
然后,青木交付 M 供应商提供的新水果。的甜蜜 j-第一个新水果是 B_j.
高桥决定选择 K 这些水果 N + M 水果按甜度降序排列,可作为礼品组合。
求 的总甜度 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
- 第一行包含商店中的水果数量 N,新送水果数量 M,以及要选择的水果数量 K,用空格分隔。
- 以下 N 行,其中 i- 第行 (1 \leq i \leq N) 含有甜味 A_i 的 i商店里的第一个水果。
- 以下 M 行,其中 j- 第行 (1 \leq j \leq M) 含有甜味 B_j 的 j-第一个新交付的水果。
输出
打印总甜度 K 在一行上选择水果。
示例输入 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