D. Илгээмж

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

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

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

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

Ярослав жижиг шуудангийн үйлчилгээ эрхэлдэг. Тэр саяхнаас илгээмжийн үйл ажиллагааны шинэ систем нэвтрүүсэн. Илгээмж бүр хайрцагтай ба өөрийн гэсэн жин болон чадалтай. Систем нь дараах байдлаар ажилладаг. Эхэндээ тавцан хоосон байгаа бөгөөд дараах дүрмээр хайрцагуудыг тавина:

  • Хэрвээ тавцан хоосон бол хайрцгыг тавцан дээр шууд тавина, харин эсрэг тохиолдолд тавцан дээрх хамгийн дээд талын хайрцаг дээр тавина.
  • Тавцан дээрх бүх хайрцагны нийт жин нь тавцангийн $S$ чадлаас ямар ч тохиолдолд хэтэрч болохгүй.
  • Тавцангийн аль ч хайрцагны чадлаас дээр нь байгаа хайрцагнуудын нийт жин нь ямар ч нөхцөлд хэтрэх ёсгүй.

Чи тавцангаас хамгийн дээд хайрцагийг л авч чадна.

Систем $n$ илгээмжийг хүлээж авдаг, $i$-р илгээмжийг яг $in_{i}$ цагт хүлээж авсан ба түүний жин болон чадал нь $w_{i}$, $s_{i}$-тэй тэнцүү. Илгээмж бүр нь $v_{i}$ боурлэс (мөнгөний нэгж) утгатай байна. Энэ утгыг авахын тулд, системд яг $out_{i}$ цагийг оруулах хэрэгтэй, эсрэг тохиолдолд Ярослав 0 боурлэс авна. Тиймэс Ярослав ямар нэг илгээмжийг авахгүй алгасаж болох ба тавцан дээр тавихгүй, илүү тодорхой хэлвэл $in_{i}$ цагт түүнийг хүргэсэн ба үүнийхээ төлөө юу ч авахгүй.

Ямар ч асуудлын үйлдлийг тэр дор нь гүйцэтгэдэг. Энэ нь илгээмжийг хүлээж авах болон хүргэх хэд хэдэн үйлдлийг ямар ч дарааллаар ижил цагт хийх боломжтой гэсэн үг юм.

$out_{i}$ цагт хүргэгдсэн илгээмжийг тэр даруй системээс гаргах ба энэ үед дараагийн үйл ажиллагааг үүнийг анхааралгүй хийнэ.

Систем нь маш нарийн бөгөөд олон илгээмж хүлээж авдаг, Яраслов энэ системийг ашиглан олж чадах хамгийн их мөнгөний хэмжээг чамаас асууж байна.

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан хоёр бүхэл $n$, $S$ ($1 ≤ n ≤ 500$, $0 ≤ S ≤ 1000$) тоог агуулна. Дараа нь $n$ мөр байх ба $i$-р мөр нь зайгаар тусгаарлагдсан таван ширхэг бүхэл тоо агуулна: $in_{i}$, $out_{i}$, $w_{i}$, $s_{i}$, $v_{i}$ ($0 ≤ in_{i} < out_{i} < 2n$, $0 ≤ w_{i}, s_{i} ≤ 1000$, $1 ≤ v_{i} ≤ 10^{6}$). Үүнд ямар ч $i$ ба $j$-н ($i ≠ j$) хувьд $in_{i} ≠ in_{j}$, эсвэл $out_{i} ≠ out_{j}$ байна.

Гаралт

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

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

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

Оролт
3 2
0 1 1 1 1
1 2 1 1 1
0 2 1 1 1
Гаралт
3
Оролт
5 5
0 6 1 2 1
1 2 1 1 1
1 3 1 1 1
3 6 2 1 2
4 5 1 1 1
Гаралт
5

Тэмдэглэл

Хоёр дахь жишээнд ($T$ бол хугацааны агшин юм):

  • $T = 0$: Эхний илгээмж ирсэн, бид эхний тавцангын дээр тавина.
  • $T = 1$: Хоёр болон гуравдугаар илгээмжүүд ирсэн, гуравдугаар илгээмжийг тавцан дээрх илгээмжийн хамгийн дээр (өөрөөр хэлбэл нэгдүгээр) байгаа илгээмжин дээр тавина, дараа нь хоёрдугаар илгээмжийг гуравдугаар илгээмжин дээр тавина. Одоо нэгдүгээр илгээмж нь $w_{2} + w_{3} = 2$ жинтэй ба гуравдугаар илгээмж $w_{2} = 1$ жинтэй.
  • $T = 2$: Бид хоёрдугаар илгээмжийг хүргэсэн ба $v_{2} = 1$ боурлэс авсан. Одоо нэгдүгээр илгээмж $w_{3} = 1$ жинтэй, гуравдугаар илгээмж 0 жинтэй.
  • $T = 3$: Дөрөвдүгээр илгээмж ирсэн. Эхлээд гуравдугаар илгээмжийг өгөөд $v_{3} = 1$ боурлэс авсан. Одоо нэгдүгээр илгээмж нь 0 жинтэй. Бид дөрөвдүгээр илгээмжийг нэгдүгээр илгээмж дээр тавина. Ингээд нэгдүгээр илгээмж $w_{4} = 2$ жинтэй боллоо.
  • $T = 4$: Тавдугаар илгээмж ирсэн. Бид тавцангийн илгээмжийн дээр тавьж чадахгүй, учир нь нэгдүгээр илгээмжийн чадал $s_{1} = 2$ тул$w_{4} + w_{5} = 3$ болсон тохиололд түүний дээр тавих боломжгүй юм. Иймээс бид тавдугаар илгээмжийг алгасна.
  • $T = 5$: Юу ч болоогүй.
  • $T = 6$: Бид дөрөвдүгээр илгээмжийг, дараа нь нэгдүгээр илгээмжийг хүргэсэн ба тэднээс $v_{1} + v_{4} = 3$ боурлэс авсан.

Чи тавдугаар илгээмжийн олонд дөрөвдүгээр илгээмжийг алгасаж болно, гэвч энэ тоиолдолд сүүлийн нийлбэр 4 боурлэс болно.

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