F. Амтлагч ба Хүндэтгэлийн зоог

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

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

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

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

Амтлагч зочдод зориулсан $n$ тавагтай хоол бүхий зоогийн танхимд ирэв. Амтлагч таваг бүр дээр хэзээ хоолоор үйлчлэх хуваарийг мэдэж байгаа.

$i$-р таваг бүрийн хувьд тэр хугацааны хоёр агшинг илэрхийлэх бүхэл тоон утгууд $a_{i}$ ба $b_{i}$-г (хүндэтгэлийн зоогийн эхнээс секундээр тооцно) мэдэж байгаа ба эдгээр нь $i$-р тавагтай хоолыг танхимд оруулах болон гаргах үеүүдийг илэрхийлнэ. Жишээлбэл хэрвээ $a_{i} = 10$ ба $b_{i} = 11$ байвал $i$-р таваг нь нэг секундын турш л идэх боломжтой байна.

Тавгууд маш ихээр орж ирэх ба тавагтай хоол идэх боломжтой байх хугацаандаа (өөрөөр танхимд байх хугацаандаа) дуусахгүй нь тодорхой.

Амтлагч $n$ таваг бүрийг амтлахыг хүсч байгаа ба ямар ч хоол орхигдуулахыг хүсэхгүй байна. Үүний тулд Амтлагч таваг бүрт ижил хугацааны амталгаа явуулна. Амталгааны үед Амтлагч хугацаа алдахгүйгээр таваг хооронд шилжиж чадна. Гэхдээ таваг хооронд шилжихдээ зөвхөн хугацааны бүхэл тоон агшинд л шилжиж чадна. Амтлагч нэгээс олон тавганд амталгаа зэрэг хийж чадахгүй. Өөр тавганд амталгаа хийж байгаад амталгаа хийж байсан тавгандаа буцаад ирж болно.

Амтлагч дээр тодорхойлсон нөхцөлүүдийг зөрчихгүйгээр аль болох их идэхийг хүсч байна. Та түүнд хүндэтгэлийн зоог дээр тавагнуудаас идэж чадах хамгийн их цагийг олж өгч тусална уу.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ $(1 ≤ n ≤ 100)$ байх буюу тавагнуудын тоо юм.

Дараагийн $n$ мөрөнд тавагнуудын мэдээллийг агуулна. $i$-р мөрөнд хоёр бүхэл тоон утга $a_{i}$ ба $b_{i}$ $(0 ≤ a_{i} < b_{i} ≤ 10000)$ байх ба $i$-р тавганы хоолыг идэх боломжтой болох хугацааны агшин болон тавгийг танхимаас гаргах агшин байна.

Гаралт

Гаралтанд хүндэтгэлийн зоог дээр Амтлагчийн идэж чадах нийт хугацааг илэрхийлэх бүхэл тоон утгыг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
3
2 4
1 5
6 9
Гаралт
6
Оролт
3
1 2
1 2
1 2
Гаралт
0

Тэмдэглэл

Эхний жишээн дээр Амтлагч хоёрдугаар тавагнаас нэг секундын турш хооллоно (хугацааны 1 агшнаас 2 агшны хооронд), дараа нь эхний тавагнаас хоёр секунд хооллоно (2-с 4-н хооронд), тэгээд эргээд хоёр дахь тавагнаас хоёр секунд хооллоно (4-с 5-н хооронд). Үүний дараа тэр гурав дахь тавагнаас хоёр секунд хооллоно (6-c 8-н хооронд).

Хоёр дахь жишээн дээр Амтлагч таваг бүрээс ядаж нэг секунд хугацаанд хооллож чадахгүй учир нь энд гурван таваг байгаа боловч тэд зөвхөн нэг секундын турш л идэх боломжтой байна (1-с 2-н хооронд).

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