/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 個の黒色のボールと M 個の白色のボールがあります。
ボールにはそれぞれ価値がつけられており、i\ (1\leq i\leq N) 個目の黒色のボールの価値は B_i、j\ (1\leq j\leq M) 個目の白色のボールの価値は W_j です。
黒色のボールの個数が白色のボールの個数以上になるようにボールを 0 個以上選ぶとき、選んだボールの価値の総和としてありうる最大値を求めてください。
制約
- 1\leq N,M\leq 2\times 10^5
- -10^9\leq B_i,W_j\leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M B_1 B_2 \ldots B_N W_1 W_2 \ldots W_M
出力
答えを出力せよ。
入力例 1
4 3 8 5 -1 3 3 -2 -4
出力例 1
19
1,2,4 個目の黒色のボールと 1 個目の白色のボールを選ぶとき、選んだボールの価値の総和は 8+5+3+3=19 となりこれが最大です。
入力例 2
4 3 5 -10 -2 -5 8 1 4
出力例 2
15
1,3 個目の黒色のボールと 1,3 個目の白色のボールを選ぶとき、選んだボールの価値の総和は 5+(-2)+8+4=15 となりこれが最大です。
入力例 3
3 5 -36 -33 -31 12 12 28 24 27
出力例 3
0
ボールを 1 つも選ばないことも可能です。
Score : 300 points
Problem Statement
There are N black balls and M white balls.
Each ball has a value. The value of the i-th black ball (1 \le i \le N) is B_i, and the value of the j-th white ball (1 \le j \le M) is W_j.
Choose zero or more balls so that the number of black balls chosen is at least the number of white balls chosen. Among all such choices, find the maximum possible sum of the values of the chosen balls.
Constraints
- 1 \leq N,M \leq 2\times 10^5
- -10^9 \leq B_i, W_j \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M B_1 B_2 \ldots B_N W_1 W_2 \ldots W_M
Output
Print the answer.
Sample Input 1
4 3 8 5 -1 3 3 -2 -4
Sample Output 1
19
If you choose the 1st, 2nd, and 4th black balls, and the 1st white ball, the sum of their values is 8+5+3+3=19, which is the maximum.
Sample Input 2
4 3 5 -10 -2 -5 8 1 4
Sample Output 2
15
If you choose the 1st and 3rd black balls, and the 1st and 3rd white balls, the sum of their values is 5+(-2)+8+4=15, which is the maximum.
Sample Input 3
3 5 -36 -33 -31 12 12 28 24 27
Sample Output 3
0
It is possible to choose no balls.