A. Шүдний эмч Женади

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

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

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

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

Женади бол Берландын хүүхдийн шүдний эмч нарын шилдгүүдийн нэг. Өнөөдөр түүн дээр $n$ хүүхэд цаг авсан ба түүний оффисийн урд жагссан байна.

Бүх хүүхдүүд шүдний эмчийн хүлээн авах дээр уйлдаг. Бид хүүхдүүдийг жагссан дарааллаар нь $1$-c $n$ хүртэлх бүхэл тоонуудаар дугаарлана. Хүүхэд бүр өөрийн гэсэн итгэлийн $p_{i}$ утгатай. Хүүхдүүд нэг нэгнийхээ араас ээлжилж оффисруу орох ба жагсаалын хамгийн эхэнд байгаа хүүхэд түрүүлж орно.

Женади $i$-р хүүхдийн шүдийг эмчилж байх үед уг хүүхэд $v_{i}$ чимээтэй уйлна. Энэ үед жагсаалын эхэнд зогсож байгаа хүүхдийн итгэл $v_{i}$ хэмжээгээр багасна, хоёр дахь хүүхдийн итгэл $v_{i} - 1$ хэмжээгээр багасна гээд цааш үргэлжилнэ. Дарааллын $v_{i}$-р хүүхдийн ард зогсож байгаа хүүхдүүд уйлах чимээг сонсохгүй учир тэдний итгэл хэвээрээ үлдэнэ.

Хэрвээ хугацааны дурын агшинд $j$-р хүүхдийн итгэл тэгээс бага болвол хүүхэд $d_{j}$ чимээтэй уйлж эхлэх ба дарааллыг орхиж эмчийн оффисруу орохгүйгээр гарцруу гүйнэ. Энэ үед $j$-р хүүхдийн ард байгаа бүх хүүхдийн итгэл $d_{j}$ хэмжээгээр буурна.

Эдгээр үйл явдлууд нь нэг нэгнийхээ араас явагдана. Нэг хүүхэд уйлснаар дараагийн хүүхэд уйлах шалтгаан болж болох буюу гинжин холбоо үүсгэж болно. Үүдний өрөө намуухан байвал дарааллын хамгийн эхэнд зогсож байгаа хүүхэд эмчийн оффисруу орно.

Шүдний эмч Женадид шүдийг нь янзлах хүүхдүүдийн тоог гаргахад туслана уу. Тэдгээрийн дугаарыг орох цагийнх нь дарааллаар хэвлэнэ үү.

Оролт

Оролтын эхний мөрөнд эерэг бүхэл тоо $n$ ($1 ≤ n ≤ 4000$) байх ба дараалалд зогсож байгаа хүүхдүүдийн тоо байна.

Дарагийн $n$ мөр бүрт гурван бүхэл тоо $v_{i}, d_{i}, p_{i}$ ($1 ≤ v_{i}, d_{i}, p_{i} ≤ 10^{6}$) байх буюу $i$-р хүүхдийн оффист уйлах дуу, үүдний өрөөнд уйлах дуу болон итгэл байна.

Гаралт

Женадигийн шүдийг нь эмчлэх хүүхдийн тоог илэрхийлэх $k$ тоог эхний мөрөнд хэвлэ.

Хоёр дахь мөрөнд хүүхдүүдийн дугаарыг өсөх дарааллаар буюу $k$ бүхэл тоог хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
5
4 2 2
4 1 2
5 2 4
3 3 5
5 1 2
Гаралт
2
1 3 
Оролт
5
4 5 1
5 3 9
4 1 2
2 1 8
4 1 9
Гаралт
4
1 2 4 5 

Тэмдэглэл

Эхний жишээн дээр Женади эхлээд эхний хүүхдийн шүдийг эмчлэх ба хүүхэд $4$ чимээтэй уйлна. Үлдсэн хүүхдүүдийн итгэл нь харгалзан $ - 2, 1, 3, 1$ болно. Иймээс хоёр дахь хүүхэд ч мөн $1$ чимээтэйгээр уйлж гарцруу гүйнэ. Үлдсэн хүүхдүүдийн итгэл нь харгалзан $0, 2, 0$ болно. Ингээд гурав дахь хүүхэд оффисруу орох ба $5$ чимээтэй уйлна. Тэгээд үлдсэн хүүхдүүд тэсэхгүй бүгд уйлж гарцруу гүйнэ.

Хоёр дахь жишээн дээр эхний хүүхэд оффисруу орох ба $4$ чимээтэй уйлна. Үлдсэн хүүхдүүдийн итгэл нь харгалзан $5,  - 1, 6, 8$ болно. Иймээс гурав дахь хүүхэд бас $1$ чимээтэй уйлж гарцруу гүйнэ. Үлдсэн хүүхдүүдийн итгэл нь харгалзан $5, 5, 7$ болно. Үүний дараа хоёр дахь хүүхэд оффисруу орж $5$ чимээтэй уйлна. Үлдсэн хүүхдүүдийн итгэл нь $0, 3$ болно. Тэгээд дөрөв дахь хүүхэд оффисруу орох ба $2$ чимээтэй уйлна. Үүнээс болж тав дахь хүүхдийн итгэл $1$ болох ба тав дахь хүүхэд хамгийн сүүлд оффисруу орно.

Сэтгэгдлүүдийг ачааллаж байна...