Алматы қала әкімдігі «Аспан горизонты» атты ірі түнгі жарықтандыру жобасын жоспарлауда. Әл-Фараби даңғылы бойында бір қатарда \(N\) аспан тіреген ғимарат тұр. Оларға солдан оңға қарап, \(i\)-ші ғимараттың биіктігі \(H_i\)-ге, ал сәулеттік сұлулығы \(B_i\) ұпайға тең.

Бас сәулетші неон жарықтандырма орнатылатын ғимараттар жиынын таңдағысы келеді. Қала панорамасы үйлесімді болуы үшін таңдалған ғимараттардың биіктіктері (солдан оңға қарай) кемімейтін реттілік құруы тиіс: әрбір келесі жарықтандырылған ғимарат алдыңғысымен бірдей немесе одан биік болуы керек.

Сәулетшіге барлық жарықтандырылған ғимараттардың жалпы сұлулығы максималды болатындай жиынды таңдауға көмектесіңіз.

Енгізу

Бірінші жолда \(N\) — ғимараттар саны берілген (\(1 \le N \le 2 \cdot 10^5\)).

Екінші жолда \(N\) бүтін сан берілген: \(H_1, H_2, \ldots, H_N\) — ғимараттардың биіктіктері (\(1 \le H_i \le 10^9\)).

Үшінші жолда \(N\) бүтін сан берілген: \(B_1, B_2, \ldots, B_N\) — ғимараттардың сұлулығы (\(1 \le B_i \le 10^9\)).

Шығару

Жалғыз бүтін санды шығарыңыз — таңдалған ғимараттардың ең жоғары жалпы сұлулығы. Жауап 32-биттік типке сыймауы мүмкін; 64-биттік бүтін санды (long long) қолданыңыз.

Мысалдар

Енгізу 1

5
1 3 2 4 3
5 3 8 2 4

Жауап 1

17

Енгізу 2

4
3 1 2 3
4 10 6 2

Жауап 2

18

Ескертпелер

Мысалдарға түсіндірме

Бірінші мысалда \(1, 3, 5\) нөмірлі ғимараттарды таңдау тиімді (1-индекстеу): биіктіктер \([1, 2, 3]\) — кемімейтін; жалпы сұлулық \(5 + 8 + 4 = 17\).

Екінші мысалда \(2, 3, 4\) нөмірлі ғимараттарды таңдау тиімді: биіктіктер \([1, 2, 3]\) — кемімейтін; жалпы сұлулық \(10 + 6 + 2 = 18\).

Ішкі тапсырмалар