問題文

JOI 高校の葵さんは，友達にお菓子を配ることにした．

葵さんには，$N$ 人の友達がおり，$1$ から $N$ までの番号が付けられている．

葵さんはアイスクリームを $X$ 個，チョコレートを $Y$ 個持っている．葵さんは，$N$ 人の友達全員にアイスクリームまたはチョコレートのいずれか一方を $1$ 個ずつ配ることにした．ここで，アイスクリームとチョコレートは合わせて $N$ 個以上であることが保証される．そのため，葵さんは友達全員にお菓子を配ることが可能である．

友達 $i$ ($1 \le i \le N$) は，アイスクリームをもらうと $A_i$ の嬉しさを，チョコレートをもらうと $B_i$ の嬉しさを得る．

このとき，葵さんの友達全員が得る嬉しさの合計としてあり得る最大値を出力せよ．

制約

• $1 \le N \le 200\,000$．
• $0 \le X \le N$．
• $0 \le Y \le N$．
• $N \le X + Y$．
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)．
• $1 \le B_i \le 10^9$ ($1 \le i \le N$)．
• 入力される値はすべて整数である．

小課題

1. ($5$ 点) $N = 1$．
2. ($5$ 点) $X = N$，$Y = 0$．
3. ($5$ 点) $X = N$，$Y = N$．
4. ($25$ 点) $X = N$，$Y = 1$．
5. ($25$ 点) $X + Y = N$．
6. ($10$ 点) $N \le 10$．
7. ($25$ 点) 追加の制約はない．

入力

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

N X Y
A_1 A_2 … A_N
B_1 B_2 … B_N

出力

葵さんの友達全員が得る嬉しさの合計としてあり得る最大値を出力せよ．

答え以外は何も出力しないこと．(入力を促す文章なども出力しないこと．)

解答形式については，練習問題やその解答例 を参考にしても良い．

入力例 1

入力

2 1 1
10 20
40 30

出力

60

葵さんがお菓子を配る方法は以下の $2$ 通りである．

• 友達 $1$ にアイスクリームを配り，友達 $2$ にチョコレートを配る場合，嬉しさの合計は $A_1 + B_2 = 10 + 30 = 40$ である．
• 友達 $1$ にチョコレートを配り，友達 $2$ にアイスクリームを配る場合，嬉しさの合計は $B_1 + A_2 = 40 + 20 = 60$ である．

この $2$ 通りのうち，嬉しさの合計が最大となるのは後者であり，そのときの嬉しさの合計は $60$ である．したがって $60$ を出力する．

この入力例は小課題 $5, 6, 7$ の制約を満たす．

入力例 2

入力

2 2 2
10 20
40 30

出力

70

葵さんがお菓子を配る方法は以下の $4$ 通りである．

• 友達 $1$ と友達 $2$ の両方にアイスクリームを配る場合，嬉しさの合計は $A_1 + A_2 = 10 + 20 = 30$ である．
• 友達 $1$ にアイスクリームを配り，友達 $2$ にチョコレートを配る場合，嬉しさの合計は $A_1 + B_2 = 10 + 30 = 40$ である．
• 友達 $1$ にチョコレートを配り，友達 $2$ にアイスクリームを配る場合，嬉しさの合計は $B_1 + A_2 = 40 + 20 = 60$ である．
• 友達 $1$ と友達 $2$ の両方にチョコレートを配る場合，嬉しさの合計は $B_1 + B_2 = 40 + 30 = 70$ である．

この $4$ 通りのうち，嬉しさの合計が最大となるのは最後の場合であり，そのときの嬉しさの合計は $70$ である．したがって $70$ を出力する．

この入力例は小課題 $3, 6, 7$ の制約を満たす．

入力例 3

入力

1 1 0
1234
5678

出力

1234

この入力例において，葵さんには友達が $1$ 人しかいない．

この入力例は小課題 $1, 2, 5, 6, 7$ の制約を満たす．

入力例 4

入力

10 10 1
314159265 358979323 846264338 327950288 419716939 937510582 97494459 230781640 628620899 862803482
534211706 798214808 651328230 664709384 460955058 223172535 940812848 111745028 410270193 852110555

出力

5867599604

出力が 32bit 整数型に収まらない場合があることに注意せよ．

この入力例は小課題 $4, 6, 7$ の制約を満たす．