D. Бүү ай, ДравДе сайхан сэтгэлтэй

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

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

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

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

«Z» хотоос «З» хот руу явж буй $n$ ачааны машин бүхий цуваа "Аймшгийн хонгил" гэгддэг нэгэн хонгилд хүрчээ. Ачааны машины жолоочдын дунд энэ хонгилд жолоочдыг ангуучилдаг ДравДе мангасын тухай цуу яриа байдаг. Зарим жолоочид эхэнд явахаас, зарим нь сүүлд явахаас айна. Ерөнхий тохиолдлыг авч үзье. Ачааны машин тус бүр дараах $4$ тоогоор тодорхойлогддог:

  • $v$ - ачааны машин, зорчигчид болон ачааны үнэ цэнэ
  • $c$ - ачааны машин дахь зорчигчдын тоо (жолоочийг оруулаад)
  • $l$ - тус ачааны машинаас өмнө хонгилд орох ёстой хүмүүсийн тоо. Ингэснээр жолооч айдсаа дарж чадна ("хэрэв мангас цувааны урдаас гарч ирвэл тэр тэднийг эхэлж иднэ" гэж бодох учраас)
  • $r$ - тус ачааны машины араас дагах ёстой хүмүүсийн тоо. Ингэснээр жолооч айдсаа дарж чадна ("хэрэв мангас цувааны ардаас гарч ирвэл тэр тэднийг эхэлж иднэ" гэж бодох учраас).

Зам нарийхан учир хэрэв ДравДе урдаас юм уу хойноос гарч ирвэл түүнээс зугтаах боломжгүй болно. Түүнээс гадна цуваанд яваа машинууд байраа сольж болохгүй. Хэдийгээр машинуудын дараалал өөрчлөгдөж болохгүй ч цуваанаас хэд хэдэн ачааны машиныг авч гаргаж, тодорхойгүй хугацаагаар хонгилын ойролцоо үлдээх боломжтой. Та цувааны ахлагчийн хувьд зарим ачааны машиныг цуваанаас гарган цувааг хонгилоор явуулах ба хонгилоор явах ачааны машинуудын үнэ цэнийн нийт хэмжээг хамгийн их байлгах хэрэгтэй.

Оролт

Эхний мөр нь цуваан дахь ачааны машины тоог харуулах $n$ ($1≤n≤10^{5}$) тоог агуулна. Дараагийн $n$ мөрүүд нь тус бүрдээ $4$ бүхэл тоог агуулна. $i$-р мөрөн дэх тоонууд нь: $i$-р ачааны машиныг тодорхойлох $v_{i}, c_{i}, l_{i}, r_{i}$ ($1≤v_{i}≤10^{4}, 1≤c_{i}≤10^{5}, 0≤l_{i}, r_{i}≤10^{5}$) тоонууд байна. Ачааны машинууд нь цувааны эхнээс $1$-ээс эхлэн дугаарлагдана.

Гаралт

Эхний мөрөнд хонгилоор гарах машинуудын тоог харуулах $k$ тоог хэвлээрэй. 2 дахь мөрөнд эдгээр ачааны машинуудын дугаарыг өсөх дарааллаар нь харуулах $k$ ширхэг тоог хэвлээрэй. Ачааны машинуудын дарааллыг өөрчилж болохгүй гэдгийг бүү мартаарай. Хэрэв хариулт нь цор ганц биш бол эдгээрээс аль нэгийг нь хэвлээрэй.

Орчуулсан: Солонго

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

Оролт
5
1 1 0 3
1 1 1 2
1 1 2 1
1 1 3 0
2 1 3 0
Гаралт
4
1 2 3 5 
Оролт
5
1 1 0 3
10 1 2 1
2 2 1 1
10 1 1 2
3 1 3 0
Гаралт
3
1 3 5 
Сэтгэгдлүүдийг ачааллаж байна...