A. Чихрээр хооллох

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

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

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

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

Олсыг хайчил тоглоомын баатар нь Ум Ном нэртэй бяцхан мангас юм. Тэр чихрэнд дуртай. Бас ямар нэгэн давхцалд! Мөн тэр өнөөдрийн асуудлын баатар юм.

Нэг өдөр Ум Ном найз Эваныд айлчлав. Эванд хоёр төрлийн (жимсний дусал болон хатуу чихрийн дусал) $n$ чихэр байсан ба $i$-р чихэр нь $m_{i}$ жинтэй, байшингийн шалнаас $h_{i}$ сантиметр өндөрт өлгөгдсөн байв. Ум Ном аль болох олон чихэр идэхийг хүсэж байв. Эхэндээ Ум Ном $x$ см өндөр үсэрч чадна. Тэр $y$ жинтэй чихэр идэх үед түүний хүч нэмэгдэж, үсрэлт нь $y$ сантиметраар нэмэгдэх болно.

Хэрвээ тэр ижил төрлийн хоёр чихэр дарааллан иддэггүй (Ум Ном хэтэрхий уйтгартай гэж үздэг) бол түүний идэж чадах хамгийн их чихэрний тоо хэд вэ?

Оролт

Эхний мөрөнд $n$, $x$ $(1 ≤ n, x ≤ 2000)$ хоёр бүхэл тоог оруулна. Эдгээр нь Эванд байгаа чихрийн тоо болон Ум Номын анхны үсрэлтийн өндөр. Дараагийн $n$ мөр бүр нь $i$-р чихрийн төрөл, өндөр, жин болох $t_{i}, h_{i}, m_{i}$ $(0 ≤ t_{i} ≤ 1; 1 ≤ h_{i}, m_{i} ≤ 2000)$ бүхэл тоонуудыг агуулна. Хэрвээ $t_{i}$ тоо 0-тэй тэнцүү бол энэ чихэр нь хатуу чихэр, эсрэг тохиолдолд жимсний чихэр байна.

Гаралт

Ум Номын идэж чадах хамгийн их чихэрний тоо болох нэг бүхэл тоог хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
5 3
0 2 4
1 3 1
0 8 3
0 20 10
1 5 5
Гаралт
4

Тэмдэглэл

$4$ чихэр идэж болох боломжтой аргуудын нэг нь $1$, $5$, $3$, $2$ дараалал юм. Энэ хувилбарыг авч үзье:

  1. Эхлээд Ум Номын үсрэлтийн өндөр $3$ байна. Тэр $1$ болон $2$-р чихэрт хүрч чадна. $1$-р чихрийг идсэн гэж үзье. Энэ чихрийн жин нь $4$, одоо түүний үсрэлтийн өндөр $3 + 4 = 7$ болж нэмэгдсэн.
  2. Одоо Ум Ном $2$ болон $5$-р чихэрт хүрч чадна. $5$-р чихрийг идсэн гэж үзье. Үүний дараа түүний үсрэлтийн өндөр $7 + 5 = 12$ болж нэмэгдсэн.
  3. Энэ үед $2$ ба $3$-р чихэрт хүрч чадна. Тэр $2$-р чихрийг идэж чадахгүй, учир нь $2$-р чихрийн төрөл өмнө идсэн чихрийн төрөлтэй ижил. Ум Ном $3$-р чихрийг идсэн, түүний үсрэлтийн өндөр нь $12 + 3 = 15$.
  4. Ум Ном $2$-р чихрийг идсэн, түүний үсрэлтийн өндөр нь $15 + 1 = 16$. Тэр $4$-р чихэрт хүрч чадахгүй.
Сэтгэгдлүүдийг ачааллаж байна...