Masala #0917

Xotira 64 MB Vaqt 3000 ms
14

Yangi yil sovg‘alari

Qorbobo va Qorqiz \(n\) ta yangi yil sovg‘asini bolalarga yetkazishi kerak. \(i\)-sovg‘ani Qorqiz \(a_i\) daqiqada tayyorlaydi, Qorbobo tayyor bo’lgan sovg’ani egasiga yetkazib berish uchun \(b_i\) daqiqa vaqt sarflaydi. Qorboboning xaltasiga bittadan ortiq sovg‘a sig‘maydi. Qorqiz ham bir vaqtni o‘zida bitta sovg‘ani tayyorlay oladi. Qorbobo va Qorqiz eng minimal qancha daqiqada barcha sovg‘alarni yetkaza olishadi?


Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son - \(n (1 ≤ n ≤ 2 * 10^5)\) kiritiladi.
Ikkinchi qatorda \(n\) ta butun son - \(a\) massiv elementlari \((1 ≤ a_i ≤ 10^9)\) kiritiladi.
Uchinchi qatorda \(n\) ta butun son - \(b\) massiv elementlari \((1 ≤ b_i ≤ 10^9)\) kiritiladi.


Chiquvchi ma'lumotlar:

Bitta butun son - barcha sovg‘alarni yetkazish uchun ketadigan minimal vaqtni chiqaring.


Misollar
# input.txt output.txt
1
3
1 3 4
4 2 10
17
2
5
4 4 30 6 2
5 1 4 30 3
47
Izoh:

1-testga izoh:

Birinchi navbatda, Qorqiz 1-sovg‘ani tayyorlaydi. So‘ng Qorbobo sovg‘ani yetkazadi, bu vaqtda esa Qorqiz 3-sovg‘ani tayyorlaydi. Qorbobo 3-sovg‘ani yetkazayotgan payti esa Qorqiz 2-sovg‘ani tayyorlaydi. Va nihoyat Qorbobo 2-sovg‘ani o‘z egasiga eltadi. Bunda ular 17 daqiqa vaqt sarflashadi. Bu eng minimal vaqt ekanligini isbotlasa bo‘ladi.