B. Хослол

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Иля дараах дүрмийн дагуу хөзрийн тоглоом тоглож байв.

Тоглогч нь хэдэн хэдэн хөзөртэй байна. Хөзөр болгон нь 2 ширхэг сөрөг биш бүхэл тоог агуулсан байх ба нэг нь хөзрийн дээр нөгөө нь хөзрийн доор байрласан байна. Тоглоомын нэг раундын эхэнд тоглогч өөрийн нэг хөзрийг тоглохоор сонгох аж. Хэрэв тоглогч хөзрөөрөө тоглож байхад түүний хөзрийн дээр байрлах тоо нь $a_{i}$ бөгөөд доор байрлах тоо нь $b_{i}$ байвал тэрээр $a_{i}$ оноотой болох бөгөөд дахин $b_{i}$ ширхэг хөзөр нэмж авах боломжтой болох юм. Түүнчлэн нэгэнт тоглосон хөзрийг хаяна.

Илүү тодорхой тайлбарлавал: уг тоглоомд тоглож болох хөзрийн тоог тоологч байх юм. Тоглоомын раундын эхэнд уг тоологч нь нэгтэй тэнцүү байна. Хөзрөөр тоглож дуусмагц тоологч нь тоглосон хөзрийн тоогоор буюу нэгээр багасах бөгөөд уг хөзрийн доор бичигдсэн тоо буюу $b_{i}$-аар ихсэх юм. Дараа нь уг хөзрийг хаяна. Хэрэв үүний дараа тоологч нь 0-тэй тэнцүү биш байвал тоглогч үлдсэн хөзрүүдээс өөр хөзөр аван тоглох боломжтой болох юм. Тоглоомын раунд нь тоологч нь 0-тэй тэнцүү болох эсвэл тоглогч нь дахин тоглох хөзөргүй болсон үед дуусна.

Мэдээж хэрэг Иля аль болох боломжит их оноо авахыг хүсжээ. Хэрэв та түүний хөзрүүдийг мэдэж байгаа бол түүнд туслан түүний авч чадах хамгийн их оноог тодорхойлж өгч чадах уу?

Оролт

Эхний мөрөнд Иля-д байгаа хөзрийн тоо болох бүхэл тоо $n$ ($1 ≤ n ≤ 1000$) өгөгдөнө.

Дараагийн $n$ мөрийн мөр болгонд 2 ширхэг сөрөг биш бүхэл тоонууд $a_{i}$ болон $b_{i}$ ($0 ≤ a_{i}, b_{i} ≤ 10^{4}$) зайгаар тусгаарлагдан өгөгдөх ба эдгээр нь харгалзан $i$-р хөзрийн дээр болон доор байрлах тоонуудыг илэрхийлнэ.

Гаралт

Дүрсэлсэн дүрмийн дагуу нэг раундын турш таны авч чадах хамгийн их оноог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
2
1 0
2 0
Гаралт
2
Оролт
3
1 0
2 0
0 2
Гаралт
3

Тэмдэглэл

Эхний жишээнд өгөгдсөн 2 хөзрийн аль нь ч танд нэмэлт хөзөр авах эрх өгөхгүй учраас та их оноо авч болох хөзрийн сонгон тоглох юм.

2-дахь жишээнд та эхлээд 3-р хөзрөөр тоглох хэрэгтэй юм. Уг хөзөр нь танд ямар ч оноо авчрахгүй ч гэсэн танд үлдсэн 2 хөзрийг авах эрх олгох юм.

Сэтгэгдлүүдийг ачааллаж байна...