問題文

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

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

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

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

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

制約

• 1 ≦ N ≦ 200 000．
• 0 ≦ X ≦ N．
• 0 ≦ Y ≦ N．
• N ≦ X + Y．
• 1 ≦ Ai≦ 109 (1 ≦ i ≦ N)．
• 1 ≦ Bi≦ 109 (1 ≦ i ≦ 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 ≦ 10．
7. (25 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N X Y
A1 A2 … AN
B1 B2 … BN

出力

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

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

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

入力例 1

2   1   1
10   20
40   30

出力例 1

60

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

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

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

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

入力例 2

2   2   2
10   20
40   30

出力例 2

70

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

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

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

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

入力例 3

1   1   0
1234
5678

出力例 3

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

出力例 4

5867599604

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

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