שובון החליט להשתמש בבינה מלאכותית יוצרת (Generative AI) כדי לסייע בפיתוח פרויקט תוכנה. הפרויקט מורכב מ-$N$ משימות. לכל משימה $i$ ($i = 1, 2, \dots, N$) יש עומס עבודה למימוש שנקבע מראש $A_i$ ומורכבות $B_i$.

שובון יכול לבצע את המשימות הללו בכל סדר שהוא. עם זאת, הוא אינו יכול לעבוד על יותר ממשימה אחת בו-זמנית.

ניתן להשלים כל משימה $i$ ($i = 1, 2, \dots, N$) באחת משתי הדרכים הבאות:

• לממש את המשימה באופן ידני. שובון כותב את הקוד בעצמו, דבר שלוקח $A_i$ יחידות זמן.
• להשתמש בבינה המלאכותית היוצרת. כדי לגרום ל-AI לייצר קוד תקין, שובון מסביר ל-AI את המשימה הנוכחית ואת כל המשימות שהושלמו קודם לכן. יהי $S$ סכום המורכבויות של כל המשימות שהושלמו קודם לכן. הכנת ההסבר הזה לוקחת $S + B_i$ יחידות זמן. לאחר מכן ה-AI מסיים את המימוש באופן מיידי, כך שלא נדרש זמן מימוש נוסף. לכן, השלמת משימה זו באמצעות ה-AI לוקחת בסך הכול $S + B_i$ יחידות זמן.

ללא תלות בשיטה שנבחרה, ברגע שמשימה $i$ מושלמת, המורכבות שלה $B_i$ נכללת בערכים העתידיים של $S$ בעת שימוש בבינה המלאכותית היוצרת.

מצאו את הזמן הכולל המינימלי הדרוש להשלמת כל המשימות.

קלט

הקלט מורכב משלוש שורות בפורמט הבא.

$$ \begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \\ &B_1 \ B_2 \ \dots \ B_N \end{aligned} $$

בשורה הראשונה נתון מספר המשימות, $N$ ($1 \le N \le 2 \times 10^5$). השורה השנייה מכילה $N$ מספרים שלמים, $A_1, A_2, \dots, A_N$, כל אחד בין $1$ ל-$10^9$ (כולל), המייצגים את עומסי העבודה למימוש של $N$ המשימות. השורה השלישית מכילה $N$ מספרים שלמים, $B_1, B_2, \dots, B_N$, כל אחד בין $1$ ל-$10^8$ (כולל), המייצגים את המורכבויות של $N$ המשימות.

פלט

הדפיסו בשורה אחת את הזמן הכולל המינימלי הדרוש להשלמת כל המשימות.

דוגמאות

קלט 1

3
10 6 10
5 2 4

פלט 1

18

קלט 2

1
4
10

פלט 2

4

קלט 3

5
100 100 100 100 100
5 1 4 2 3

פלט 3

35

קלט 4

12
18 7 25 12 30 5 16 22 9 28 14 20
6 11 2 8 1 13 5 3 10 4 9 7

פלט 4

118

הערה

עבור קלט לדוגמה 1, נבחן שימוש בבינה המלאכותית היוצרת עבור משימות $2$ ו-$3$ בסדר זה, ולאחר מכן מימוש ידני של משימה $1$.

• כאשר מתחילים את משימה $2$, אף משימה טרם הושלמה. משימה זו לוקחת $0 + B_2 = 2$ יחידות זמן.
• כאשר מתחילים את משימה $3$, משימה $2$ כבר הושלמה. משימה זו לוקחת $B_2 + B_3 = 2 + 4 = 6$ יחידות זמן.
• לבסוף, מימוש ידני של משימה $1$ לוקח $A_1 = 10$ יחידות זמן.

כך ניתן להשלים את כל המשימות ב-$2 + 6 + 10 = 18$ יחידות זמן, שזהו המינימום האפשרי.