RoboContest

Xotira 64 MB Vaqt 1000 ms

14

Maximal Qiymat

Tasavvur qiling, siz RoboLand kompaniyasi boshlig'isiz. Bugun bu kompaniyangiz yong'in ostida. Siz bu kompaniyangizni turli xonalarida qimmatbaho(olovda yonuvchi) taqinchoqlar saqlaysiz. Bu taqinchoqlar soni $N$ ta bo'lib, har birining siz uchun alohida o'rni bor, ya'ni $i-$ taqinchoq siz uchun $v_i$ qiymatga ega. Siz bu xonalarning uzoqligini inobatga olgan xolda, $i-$ xonaga borish uchun $T_i$ vaqt ketishini bilib oldingiz. Yong'in boshlangandan $S_i$ vaqt o'tib $i-$ xona yonib bitadi. Sizning vazifangiz, iloji boricha ko'p qiymatli taqinchoqlarni saqlab qolishdan iborat!!!

!!! Diqqat !!! $T_i\geq S_i$ holatda siz $i-$ taqinchoqni saqlashga ulgura olmaysiz)

Kiruvchi ma'lumotlar:

Birinchi qatorda $N$ soni kiritiladi.

Keyingi $N$ ta qatorda mos ravishda $T_i, ~S_i$ va $v_i$ sonlari beriladi.

$1 \leq N \leq 2*10^3$
$1 \leq T_i \leq 20$
$1 \leq S_i \leq 2 * 10^3$
$1 \leq v_i \leq 10^9$

Chiquvchi ma'lumotlar:

Yagona qatorda, siz saqlab qolishingiz bo'lgan maksimal qiymatlar yig'indisini chop eting!

Misollar

#	input.txt	output.txt
1	3 3 7 4	11
2	2 5 6 1	1

Izoh:

1-testga Izoh:

Siz istalgan 2ta taqinchoqni saqlab qola olasiz, Masalan: Birinchi bo'lib 3-taqinchoqni saqlab qolamiz. So'ng hozirgi vaqt 3ga teng bo'ladi. Keyin esa birinchi taqinchoqni olamiz va 6-unit vaqtda u xonadan chiqamiz. Ammo, biz ikkinchi taqinchoqqa endi ulgurmaymiz. Demak hozir bizda 6 + 4 = 10 qiymatga ega taqinchoqlar saqlab qolindi. Ammo bu optimal yo'l emas.

Optimal yo'l:

Birinchi bo'lib 2-taqinchoqni olib, so'ng 3-taqinchoqga o'tamiz. 1-taqinchoqqa borgunimizcha esa vaqt 8-unitda bo'ladi, demak bora olmaymiz. Bizdagi qiymat 6 + 5 = 11;

Ikkinchi test uchun optimal yo'l:

Ikkinchi xonaga borganimiz zahoti xona yonadi. Shuning uchun birinchi bo'lib birinchi xonaga yo'l olamiz va taqinchoqni olishga ulguramiz. Javob 1;

Testlar misollardagidan farq qilishi mumkin!

RoboContest

Masala H

Maximal Qiymat