Шобон бағдарламалық жобаны әзірлеуге көмектесу үшін генеративті жасанды интеллектті (ЖИ) пайдалануды ұйғарды. Жоба $N$ тапсырмадан тұрады. Әрбір $i$ ($i = 1, 2, \dots, N$) тапсырмасының алдын ала белгіленген іске асыру еңбек сыйымдылығы $A_i$ және күрделілігі $B_i$ бар.

Шобон бұл тапсырмаларды кез келген ретпен орындай алады. Алайда ол бір уақытта бірнеше тапсырмамен айналыса алмайды.

Әрбір $i$ ($i = 1, 2, \dots, N$) тапсырмасын келесі екі тәсілдің бірімен аяқтауға болады:

• Тапсырманы қолмен іске асыру. Шобон кодты өзі жазады, бұл $A_i$ уақыт бірлігін алады.
• Генеративті ЖИ пайдалану. ЖИ дұрыс код генерациялауы үшін Шобон оған ағымдағы тапсырманы және бұрын аяқталған барлық тапсырмаларды түсіндіреді. Бұрын аяқталған барлық тапсырмалардың күрделіліктерінің қосындысын $S$ деп белгілейік. Осы түсіндірмені дайындауға $S + B_i$ уақыт бірлігі кетеді. Содан кейін ЖИ іске асыруды лезде аяқтайды, сондықтан қосымша іске асыру уақыты қажет емес. Осылайша, бұл тапсырманы ЖИ көмегімен аяқтауға барлығы $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$ тапсырманың іске асыру еңбек сыйымдылығын білдіретін, әрқайсысы $1$ мен $10^9$ аралығындағы (шеткі мәндерді қоса алғанда) $N$ бүтін сан $A_1, A_2, \dots, A_N$ берілген. Үшінші жолда $N$ тапсырманың күрделілігін білдіретін, әрқайсысы $1$ мен $10^8$ аралығындағы (шеткі мәндерді қоса алғанда) $N$ бүтін сан $B_1, B_2, \dots, B_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$ уақыт бірлігінде аяқтауға болады, бұл — мүмкін болатын ең кіші мән.