- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
بهرام و محسن که تصمیم گرفته بودند با کمک یکدیگر تدریس کلاس طراحی الگوریتم ها را بر عهده بگیرند به تازگی با یک مشکل اساسی مواجه شدهاند و قرار است راهشان را از هم جدا کنند. ریشهی مشکل نگرش نابخردانهی محسن در تشخیص استعداد یک دانشجو در طراحی الگوریتم است. بهرام بدرستی معتقد است که استعداد طراحی الگوریتم دانشجویان با میزان استعداد آنها در ریاضیات گسسته رابطهی مستقیم دارد. اما محسن میگوید دانشجویی که ریاضیات پیوسته را بهتر بفهمد طراح الگوریتم بهتری خواهد شد. بدین ترتیب قرار بر آن شد که دانشجویان کلاس را به دو گروه تقسیم کرده و هر کدام تدریس گروهی را به عهده بگیرند. تقسیم اعضای کلاس بدین صورت است که هر کس در نوبت خود یک دانشجو را انتخاب میکند سپس نوبت انتخاب را به دیگری واگذار میکند. این رویه تا انتخاب شدن تمام دانشجویان ادامه دارد. از آنجایی که بهرام اخلاقی پهلوانی دارد و روی خامی محسن حساب ویژهای باز کرده است اجازه میدهد اولین انتخاب بر عهدهی محسن باشد. محسن نابخرد از استراتژی خبیصانه استفاده میکند. به این صورت که هر بار از بین دانشجویان باقیمانده فردی که بیشترین استعداد ریاضیات پیوسته را دارد انتخاب میکند. اگر چندین دانشجو با این شرایط وجود داشته باشد، محسن یکی از آنها را به دلخواه خودش انتخاب میکند. بهرام به دلیل شناخت عمیقی که از محسن دارد خبیصانه بودن او را حدس زده و میخواهد بداند بیشترین مقدار ممکن برای مجموع استعداد ریاضیات گسسته دانشجویان انتخابی خودش، مستقل از حرکات محسن، چند است. با محاسبهی این مقدار به کمک بهرام بشتابید.
ورودی
در خط اول ورودی عدد \(n\) که بیانگر تعداد دانشجویان است به شما داده میشود. \[1 \leq n \leq 100 \, 000\]
در هر یک از خطوط دوم و سوم به ترتیب \(n\) عدد صحیح \(a_1, a_2, \dots, a_n\,\) و \(b_1, b_2, \dots, b_n\,\) داده میشود که \(a_i\) بیانگر استعداد دانشجوی \(i\) در ریاضیات پیوسته و \(b_i\) بیانگر میزان استعداد دانشجوی \(i\) در ریاضیات گسسته است.
\[1 \leq a_i, b_i \leq 10^9\]
خروجی
در خروجی بیشترین مقدار ممکن برای مجموع استعداد ریاضیات گسسته دانشجویان انتخابی توسط بهرام را با فرض خبیصانه بودن استراتژی محسن چاپ کنید.
مثالها
ورودی نمونه ۱
3
1 8 4
12 11 1
خروجی نمونه ۱
12
ورودی نمونه ۲
5
1 2 3 4 5
2 3 4 5 6
خروجی نمونه ۲
8