e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin kəməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

Полуфинал Республиканской олимпиады Азербайджана 2018-2019

Dino və putalar

123.jpg

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 – siai 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
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
1
5 6
4 3

Çıxış verilənləri #1
10
Giriş verilənləri #2
2
3 6
7 1
4 9
10 11

Çıxış verilənləri #2
32
Mənbə Azərbaycan Respublika Olimpiadasının yarımfinalı 2019-2020