نص المسألة

قررت آوي من مدرسة JOI الثانوية توزيع الحلوى على أصدقائها.

لدى آوي $N$ من الأصدقاء، مرقّمين من $1$ إلى $N$.

تمتلك آوي $X$ من المثلجات و $Y$ من قطع الشوكولاتة. قررت آوي أن توزع قطعة حلوى واحدة ($1$) — إما مثلجات أو شوكولاتة — لكل واحد من أصدقائها البالغ عددهم $N$. هنا، من المضمون أن إجمالي عدد المثلجات والشوكولاتة هو $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

لاحظ أن المخرجات قد لا تتسع في نوع عدد صحيح بحجم 32 بت.

مثال الإدخال هذا يحقق قيود المهام الفرعية $4, 6, 7$.