Masala #0177

Xotira 128 MB Vaqt 2500 ms Qiyinchiligi 80 %
3.9 (Baholar 14)
14
Muallif: Sirojiddin

  

Super chiptalar

Shermatning tug’ilgan kunida unga avtobus uchun chiptalar sovg’a qilishdi. Shermat boshida ozroq xafa bo’lgandi, lekin chiptalar oddiy emas balki super chiptalar ekanligini ko’rganidan keyin ancha taskin topdi.

Hozirda uning qo’lida mm ta chipta bor va chiptalar 3 xil turga bo’linadi:
1. Bu chipta orqali aa bekatdan bb bekatgacha borsa bo’ladi.
2. Bu chipta orqali aa bekatdan [l,r][l,r] oraliqdagi ixtiyoriy bekatga borsa bo’ladi.
3. Bu chipta orqali esa [l,r][l,r] oraliqdagi ixtiyoriy bekatdan aa bekatga borsa bo’ladi.

Har bir chipta uchun avtobus qancha vaqt harakatlanishi ko’rsatilgan. Bekatlar soni jami nn ta bo’lib, dastlab Shermat ss - bekatda turibdi. Shermat ss - bekatdan qolgan bekatlarga eng kamida qancha vaqt sarflab yetib olish mumkinligiga qiziqmoqda. Shaharda avtobus reyslari shunchalik ko’pki bekatdan bir avtobusdan tushib boshqasiga o’tirishga ketgan vaqtni 0 deb hisoblash mumkin.


Kiruvchi ma'lumotlar:

Birinchi qatorda 3 ta butun son - nn, mm, va ss – bekatlar soni, chiptalar soni va Shermat turgan bekat beriladi (1n,m105,1sn)(1 ≤ n, m ≤ 10^5, 1 ≤ s ≤ n). Keyingi mm ta qatorda chiptalar tavsifi kiritiladi va ular quyidagicha ifodalanadi:

  • 1 a b t1 \space a \space b \space t - bu birinchi turli chipta bo'lib, bu chipta orqali aa bekatdan bb bekatga tt vaqtda borish mumkin.
  • 2 a l r t2 \space a \space l \space r \space t - bu ikkinchi turli chipta bo'lib, bu chipta orqali aa bekatdan [l,r][l, r] oraliqdagi ixtiyoriy bekatga tt vaqtda borish mumkin.
  • 3 a l r t3 \space a \space l \space r \space t - bu uchinchi turli chipta bo'lib, bu chipta orqali [l,r][l, r] oraliqdagi ixtiyoriy bekatdan aa bekatga tt vaqtda borish mumkin.

Chiquvchi ma'lumotlar:

Yagona qatorda probel bilan ajratilgan nn ta sonni chiqaring, ii - son ss bekatdan ii - bekatgacha borish mumkin bo'lgan eng qisqa vaqtga teng bo'lsin, agar borishni iloji yo'q bo'lsa 1-1 chiqaring.


Misollar
# input.txt output.txt
1
3 5 1
2 3 2 3 17
2 3 2 2 16
2 2 2 3 3
3 3 1 1 12
1 3 3 17
0 28 12 
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin