TATU Urganch filiali binosi Urganch shahrining Al-Xorazmiy ko’chasida joylashgan. Bu ko’chadan 3-raqamli avtobuslar harakatlanadi. Avtobus haydovchilari yo’lovchilarga qulaylik yaratish maqsadida avtobuslarga qo’shimcha o’rindiqlarni o’rnatishni rejalashtirishmoqda. Al-Xorazmiy ko’chasi burilishlarsiz ya’ni to’g’ri chiziq shaklida bo’lib, avtobus haydovchilari o’zlariga qulay bo’lishi uchun son o’qi shaklida ko’chaning koordinatalarni belgilab qo’yishgan. Bunda avtobuslar son o’qining musbat yo’nalishida harakatlanadi. Haydovchilarda yo’lovchilar eng ko’p bo’lgan paytdagi ma’lumot mavjud. Bu ma’lumotga ko’ra avtobus haydovchisi n ta bekatdan yo’lovchilarni mindirgan, ya’ni s_i koordinatada joylashgan bekatdan a_i ta yo’lovchi mingan va ular e_i koordinatadagi bekatda tushib qolgan. Avtobus haydovchilari bu ma’lumotdan foydalangan holda yo’lovchilar eng ko’p bo’lgan holatda ham hamma yo’lovchilarga o’rindiqlar yetishi uchun avtobusda eng kamida qancha o’rindiq bo’lishi kerak ekanligini aniqlashmoqchi. Bu avtobusga TATU Urganch filiali talabalari ko’p minishadi, shuning uchun ham avtobus haydovchilari ulardan bu masalani yechishda yordam so’rashmoqda. Siz ham bu masalani yechishga urinib ko’ring balki talabalardan oldinroq bu masalaning yechimini toparsiz.

Eslatma:Avtobus bekatda to’xtagan paytda dastlab tushishi kerak bo’lgan yo’lovchilar avtobusdan tushadi va ulardan keyin minmoqchi bo’lgan yo’lovchilar avtobusga minadi.

Kiruvchi ma’lumotlar: Birinchi satrda n butun son avtobus haydovchisi yo’lovchilarni mindirgan bekatlar soni (1 ≤ n ≤ 100). Keyingi n ta qatorda 3 tadan butun son, s_i - avtobus to’xtagan i-bekatning koordinatasi, e_i - bu bekatda mingan yo’lovchilar tushib qolgan bekatning koordinatasi va a_i - bu bekatda mingan va e_i koordinatadagi bekatda tushib qolgan yo’lovchilar soni (-10⁹ ≤ s_i < e_i ≤ 10⁹, 1 ≤ a_i ≤ 10⁴).

Chiquvchi ma’lumotlar: Yagona qatorda bitta butun son avtobuslarga o’rnatish lozim bo’lgan minimal o’rindiqlar soni.

6

6 8 1

-1 3 3

5 9 4

-6 7 2

7 8 1

6 11 10

Izoh: Yuqoridagi testda haydovchi dastlab -6 koordinatagi bekatdan 2 ta yo’lovchini mindiradi (bunda avtobusdagi yo’lovchilar soni 2 ga teng bo’ladi), keyin -1 koordinatada joylashgan bekatdan 3 ta yo’lovchi minadi (bunda avtobusdagi yo’lovchilar soni 5 ga teng bo’ladi), 3 koordinatada joylashgan bekatda -1 koordinatada joylashgan bekatdan mingan 3 ta yo’lovchi tushib qoladi (bunda avtobusdagi yo’lovchilar soni 2 ga teng bo’ladi), 5 koordinatada joylashgan bekatdan 4 ta yo’lovchi minadi (bunda avtobusdagi yo’lovchilar soni 6 ga teng bo’ladi), 6 koordinatada joylashgan bekatdan 8 koordinatada joylashgan bekatga boradigan 1 ta va 11 koordinataga boradigan 10 ta jami 11 ta yo’lovchi minadi (bunda avtobusdagi yo’lovchilar soni 17 ga teng bo’ladi), 7 koordinatagi bekatda 2 ta yo’lovchi tushadi va 1 ta yo’lovchi minadi (bunda avtobusdagi yo’lovchilar soni 16 ga teng bo’ladi), keyingi bekatlarda yo’lovchilar minmaydi. Bunda avtobusdagi yo’lovchilar eng ko’p bo’lgan paytda ularning soni 17 ga teng bo’lgan, shuning uchun ham minimal 17 ta o’rindiq bo’lishi kerak.