Televizorius
면접 대비시간 제한1초메모리 제한1024 MB
하루 동안 방송되는 여러 프로그램의 시작과 끝 시각이 주어지고, V초 저장 공간과 동시 K개 녹화 제한이 있을 때, 모든 프로그램을 다 볼 수 있는 가장 이른 종료 시각을 구한다.
문제
Jūratė turi naujos kartos televizorių, kuris leidžia jai ne tik tiesiogiai žiūrėti laidas, bet ir jas įrašyti. Televizorius nėra tobulas – jo atmintyje telpa tik V sekundžių vaizdo įrašų.
Jūratė gali žiūrėti laidą tiesiogiai, bei tuo pačiu metu televizorius gali įrašyti iki K kitų tuo pačiu metu rodomų laidų. Televizoriaus atmintyje yra saugomos tik dar neperžiūrėtos laidų sekundės. Taigi jeigu Jūratė nežiūri laidos tiesiogiai, o žiūri įrašą, kiekviena peržiūrėta sekundė yra iškart ištrinama iš televizoriaus atminties.
Jūratė gali žiūrėti laidas dalimis – ji gali dabar žiūrimą laidos įrašą sustabdyti ir pratęsti jį žiūrėti vėliau. Taip pat Jūratė turi galimybę žiūrėti laidą, kuri šiuo metu yra įrašoma.
Jūratė nori peržiūrėti laidą teisinga tvarka – ankstesnė laidos sekundė turi būti peržiūrėta anksčiau nei vėlesnė. Taip pat Jūratė nenori praleisti nei vienos laidos sekundės, todėl ji žiūrės laidas tol, kol peržiūrės visas laidų sekundes.
Jūratė turi sąrašą vienos kalendorinės paros TV laidų, kurias ji nori peržiūrėti. Nustatykite, ar įmanoma Jūratei peržiūrėti visas norimas laidas, ir jei taip, kada anksčiausiai ji gali baigti jas žiūrėti.
입력
Pirmoje eilutėje pateikiami trys sveikieji skaičiai: laidų, kurias Jūratė nori pažiūrėti, skaičius N, televizoriaus atminties kiekis V sekundėmis ir didžiausias vienu metu įrašomų laidų skaičius K.
Tolesnėse N eilučių pateikiama po du sveikuosius skaičius: Jūratės norimos pažiūrėti laidos pradžios Si ir pabaigos Ei laikas sekundėmis.
출력
Jei Jūratei pavyks peržiūrėti visas norimas laidas, išveskite anksčiausią įmanomą laiką T sekundėmis kada ji gali pabaigti žiūrėti visas laidas. Išvedamas laikas skaičiuojamas nuo paros, kurią buvo rodomos laidos, pradžios.
Jei Jūratė negali peržiūrėti visų norimų laidų, išveskite NEGALIMA.
Atsakymas gali viršyti 232 sekundžių, dėl to jį rekomenduojama saugoti 64 bitų sveikųjų skaičių tipuose.
제한
- 1 ≤ N ≤ 1 000 000
- 1 ≤ K ≤ 1 000 000
- 0 ≤ V ≤ 1 000 000 000
- 0 ≤ Si < Ei ≤ 86 400