Yuxarıda gördüyünüz yumurta şokoladlar dinozavrların dilində puta adlanır. Dino puta yeməyi çox sevir. Bu onun üçün əsl enerji mənbəyidir, həm də o putalardan çıxan oyuncaqlardan kolleksiya toplayır. Bu gün Dino növbəti n gün ərzində yeməsi üçün 2•n sayda puta aldı. O səhər bir, axşam da bir puta yeməyi özü üçün həyat tərzinə çevirib. Bu onun enerjisini yüksək saxlamağa imkan verir. Dinonun aldığı putalar möcüzəlidir, onlar səhər yeyildikdə ayrı, axşam yeyildikdə ayrı enerji verə bilər. Belə ki, hər bir puta üçün onun səhər və axşam verdiyi enerji bizə məlumdur. Dino çox ağıllıdır və o n gün ərzində bu putaları elə ardıcıllıqla yeməyi planlaşdırır ki, bu müddətin sonunda putalardan əldə etdiyi enerji maksimum olsun. Dinonun putalardan əldə edə biləcəyi maksimum enerjini tapın.

Giriş verilənləri

Bİrinci sətirdə günlərin sayını göstərən bir tam ədəd – n, növbəti 2•n sayda sətrin hər birində isə müvafiq putanın səhər və axşam verdiyi enerjini göstərən iki tam ədəd – si və ai verilir.

Çıxış verilənləri

Çıxışa bir tam ədəd – Dinonun putalardan əldə edə biləcəyi maksimum enerjini verin.

Məhdudiyyətlər

• 1 ≤ n ≤ 105
• 1 ≤ si, ai ≤ 109