E. Дотуур байр

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

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

оролт input.txt

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

Вася Бэрландын их сургуульд суралцаж эхэлсэн ба дотуур байранд оржээ. Хичээлийн улирал $n$ өдөртэй ба өдөр бүр ээж аав нь түүнд хоол явуулдаг. $i$-дэх өдөр түүнд $a_{i}$ килограмм хоол ирдэг ба тэр өдрөө эсвэл маргааш нь идэх боломжтой байдаг байна. Учир нь илүү удаавал хоол нь муудах юм.

Өдөр бүр Вася $v$ килограмм хоол иддэг. Васягийн эцэг эх түүнийг өлсөхийг зөвшөөрдөггүй тул хангалттай хоол явуулдаг байна. Вася $m$ найзтай ба тэд нар заримдаа түүнтэй цуг хонодог. Тэдгээр найзуудыг $1$-ээс $m$ хүртэл дугаарлая. $j$-р найз нь Васятай $l_{j}$-ээс $r_{j}$ өдөр хүртэл цуг хонодог ба өдөрт $f_{j}$ килограмм хоол иддэг. Васягийн найзууд ихэнхидээ зоогийн газар хооллодог. Гэхдээ зарим өдөр өгөөмөр Вася тэднийг дайлдаг. Өдөр бүр Вася түүнтэй цуг хонож байгаа зарим найзууддаа хоол өгч болох ба өгөхгүй байсан ч болно.

Вася $j$-р найзаа дайлахаар шийдсэн бол $f_{j}$ килограмм хоол өгдөг ба тэгэх болгонд түүний нэр хүндийн зэрэг нь нэгээр нэмэгддэг байна. Вася нэг өдөрт нэг найзаа олон дайлж болохгүй. Түүнчлэн өдөрт яг л $v$ килограмм хоол иддэг байна.

Вася нэр хүндээ хамгийн их байлгахын тулд өдөр бүрт хэн хэнд хоол өгөх ёстойгоо мэдэхийг хүсчээ. Тэрээр шинэ оюутан тул түүний анхны нэр хүндийн зэрэг нь $0$ байгаа.

Оролт

Эхний мөрөнд $n$ ба $v$ ($1 ≤ n, v ≤ 400$) гэсэн хоёр бүхэл тоо байна.. Дараагийн мөрөнд $n$ ширхэг $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 400$) бүхэл тоонууд зайгаар тусгаарлагдан өгөгдөнө. $a_{i}$ нь $i$ дэх өдрийн өглөө $a_{i}$ килограмм хоол ирсэнийг илэрхийлнэ. Энэ хоолыг $i$ юм уу $i+1$ дэх өдрүүдэд идэж болно (тэгээд хоол муудна). Өгөгдөл Вася найзуудыгаа дайлахгүй байх үед өдөр бүр $v$ килограмм хоол идэж чаддаг байхаар өгөгдөнө.

Дараагийн мөрөнд найзуудынх нь тоог илэрхийлэх бүхэл тоо $m$ ($1 ≤ m ≤ 400$) өгөгдөнө. Түүний дараагийн $m$ мөрөнд мөр бүрд Васягийн найзуудын тодорхойлолт байх буюу $j$-дэх мөрөнд $l_{j}, r_{j}, f_{j}$ ($1 ≤ l_{j} ≤ r_{j} ≤ n, 1 ≤ f_{j} ≤ 400$) бүхэл тоонууд зайгаар тусгаарлагдсан өгөгдөнө.

Гаралт

Эхний мөрөнд Васягийн олж чадах хамгийн их нэр хүндийн зэргийг хэвлэнэ. Дараагийн $n$ мөрөнд Вася өдөр бүр аль найзыгаа дайлах тухай мэдээллийг хэвлэнэ. $i$-дэх мөрөнд нь эхлээд энэ өдөр Васягийн дайлах ёстой найзынх нь тоог хэвлэнэ, дараа нь тэдгээр найзуудых нь дугааруудыг хэвлэ. Найзуудын дугаарыг дурын дарааллаар хэвлэ. Хэрэв олон боломжит хариу байгаа бол аль нэгийг нь л хэвлэхэд болно.

Орчуулсан: Бат-Од

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

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