/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君は料理コンテストに出場します。コンテストでは N 個の食材を使って料理を作ります。
食材には 1 から N までの番号がついており、i 番目の食材のおいしさは A_i です。高橋君は各食材について代わりの食材を 1 つずつ用意しており、i 番目の食材を代わりの食材に入れ替えると、おいしさが B_i に変わります。
コンテストのルールにより、高橋君は N 個の食材の中からちょうど K 個を選び、それらを代わりの食材に入れ替えなければなりません。入れ替えなかった食材のおいしさはそのまま A_i です。
料理全体のおいしさは、入れ替え後の N 個の食材のおいしさの総和で決まります。入れ替える K 個の食材をうまく選んだとき、料理全体のおいしさの最大値を求めてください。
制約
- 1 \leq K \leq N \leq 3 \times 10^5
- -10^9 \leq A_i \leq 10^9
- -10^9 \leq B_i \leq 10^9
- 入力はすべて整数である
入力
N K A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
- 1 行目には、食材の個数を表す N と、入れ替える食材の個数を表す K が、スペース区切りで与えられる。
- 2 行目には、現在の食材のおいしさを表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
- 3 行目には、代わりの食材のおいしさを表す B_1, B_2, \ldots, B_N が、スペース区切りで与えられる。
出力
料理全体のおいしさの最大値を 1 行で出力してください。
入力例 1
4 2 5 2 4 1 3 10 1 7
出力例 1
26
入力例 2
3 2 8 -1 5 4 -3 2
出力例 2
7
入力例 3
8 4 3 -5 12 7 0 9 -2 4 8 -10 6 20 -1 9 5 -3
出力例 3
53
入力例 4
20 9 4 -7 13 0 25 -12 8 19 -3 6 11 -1 14 -9 2 17 5 -6 10 1 9 -20 5 7 30 -4 -8 18 12 6 -2 3 16 -15 20 10 -1 14 0 1
出力例 4
181
入力例 5
1 1 -1000000000 1000000000
出力例 5
1000000000
Score : 333 pts
Problem Statement
Takahashi is participating in a cooking contest. In the contest, he will prepare a dish using N ingredients.
The ingredients are numbered from 1 to N, and the deliciousness of the i-th ingredient is A_i. Takahashi has prepared one substitute ingredient for each ingredient. If he replaces the i-th ingredient with its substitute, its deliciousness changes to B_i.
According to the contest rules, Takahashi must choose exactly K out of the N ingredients and replace them with their substitute ingredients. The deliciousness of ingredients that are not replaced remains A_i.
The overall deliciousness of the dish is determined by the sum of the deliciousness values of all N ingredients after replacement. Find the maximum possible overall deliciousness of the dish when the K ingredients to replace are chosen optimally.
Constraints
- 1 \leq K \leq N \leq 3 \times 10^5
- -10^9 \leq A_i \leq 10^9
- -10^9 \leq B_i \leq 10^9
- All input values are integers
Input
N K A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
- The first line contains N, the number of ingredients, and K, the number of ingredients to replace, separated by a space.
- The second line contains A_1, A_2, \ldots, A_N, the deliciousness values of the current ingredients, separated by spaces.
- The third line contains B_1, B_2, \ldots, B_N, the deliciousness values of the substitute ingredients, separated by spaces.
Output
Print the maximum possible overall deliciousness of the dish in one line.
Sample Input 1
4 2 5 2 4 1 3 10 1 7
Sample Output 1
26
Sample Input 2
3 2 8 -1 5 4 -3 2
Sample Output 2
7
Sample Input 3
8 4 3 -5 12 7 0 9 -2 4 8 -10 6 20 -1 9 5 -3
Sample Output 3
53
Sample Input 4
20 9 4 -7 13 0 25 -12 8 19 -3 6 11 -1 14 -9 2 17 5 -6 10 1 9 -20 5 7 30 -4 -8 18 12 6 -2 3 16 -15 20 10 -1 14 0 1
Sample Output 4
181
Sample Input 5
1 1 -1000000000 1000000000
Sample Output 5
1000000000