F. Шинэ жилийн худалдан авалт

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

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

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

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

Дохюн хүнсний дэлгүүр ажиллуулж байгаа. Тэр $1$-ээс $n$ хүртэлх бүхэл тоогоор дугаарлагдсан $n$ барааг зардаг. Эдгээрийн $i$-р ($1≤i≤n$) нь $c_{i}$ долларын үнэтэй бөгөөд хэрвээ би үүнийг худалдан авбал миний сэтгэл ханамж $h_{i}$-ээр өснө. Барааг шинэлэг байлгахын тулд $p$ нэгж хугацаанд харагдана. Дохюн $i$-р барааг $t_{i}$ цагт гаргахад худалдан авагч $i$-р барааг зөвхөн $t_{i}$-ээс $t_{i}+(p-1)$ цагийн хооронд авах боломжтой. Түүнчлэн худалдан авагч бүр нэг ижил барааг нэгээс илүү авч болохгүй.

Би шинэ жилийн үдэшлэгтээ зориулж Дохюны хүнсний дэлгүүрээс зарим нэг барааг худалдаж авч, сэтгэл ханамжаа хамгийн дээд түвшинд хүртэл дээшлүүлэхийг хүсч байна. Яагаад гэвэл би үнэхээр завгүй байдаг тул хүнсний дэлгүүрээр зөвхөн ганц удаа, маш богино хугацаанд л орох боломжтой. Өөрөөр хэлбэл, хэрвээ би дэлгүүрт $t$ цагт ирвэл зөвхөн $t$ цагт байгаа барааг л худалдан авна. Гэхдээ төсөв хүрвэл би боломжоороо олон бараа авч болно. Дэлгүүрийн дүрмээс шалтгаалж би нэг бараанаас олон удаа авч чадахгүй. Бүх төсвийг зарцуулах шаардлагагүй.

Би $(a_{j}, b_{j})$ бүхэл тоон $q$ ширхэг хослолуудын жагсаалт гаргасан. Энд $a_{j}$ нь дэлгүүрт очих цаг, $b_{j}$ нь дэлгүүрт ашиглах долларын хэмжээ юм. Хослол бүрт олж авах хамгийн их сэтгэл ханамжийн хэмжээг мэдмээр байна. Гэхдээ маш олон хослол байгаа тул би бүгдийг нь тооцож чадахгүй байна. Та надад туслах уу?

Оролт

Эхний мөр нь барааны тоо болон бараа тус бүрийн харагдах хугацааг харуулах хоосон зайгаар тусгаарлагдсан $n$ ба $p$ ($1≤n≤4000$, $1≤p≤10000$) хоёр бүхэл тоо агуулна.

Дараагийн $n$ мөрүүд бараануудыг тодорхойлно. $i$-р ($1≤i≤n$) мөр нь $i$-р барааны үнэ, $i$-р барааны сэтгэл ханамжийн хэмжээ болон $i$-р барааны харагдаж эхлэх хугацааг харуулах хоосон зайгаар тусгаарлагдсан $c_{i}$, $h_{i}$, $t_{i}$ ($1≤c_{i}, h_{i}≤4000$, $1≤t_{i}≤10000$) гурван бүхэл тоог агуулна.

Дараагийн мөр нь хослолуудын тоог харуулах $q$ ($1≤q≤20000$) бүхэл тоог агуулна.

Дараагийн $q$ мөрүүд нь хослолуудыг тодорхойлно. $j$-р ($1≤j≤q$) мөр нь дэлгүүрт очсон цаг болон төсвийг харуулах хоосон зайгаар тусгаарлагдсан $a_{j}$, $b_{j}$ ($1≤a_{j}≤20 000$, $1≤b_{j}≤4000$) бүхэл тоог агуулна.

Гаралт

Хослол бүрт зарим барааг худалдаж авснаар олж авч болох хамгийн их сэтгэл ханамжийн хэмжээг агуулсан мөрийг хэвлээрэй.

Орчуулсан: Солонго

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

Оролт
4 4
2 3 2
3 5 1
4 7 2
11 15 5
4
1 3
2 5
2 6
5 14
Гаралт
5
8
10
18
Оролт
5 4
3 2 1
7 4 4
2 1 2
6 3 5
3 2 2
10
1 5
2 5
4 8
4 9
4 10
5 8
5 9
5 10
8 4
7 9
Гаралт
2
3
5
5
6
4
5
6
0
4

Тэмдэглэл

Эхний жишээг авч үзье.

  1. Цаг $1$ болж байхад зөвхөн $2$-р бараа боломжтой байна. Би $2$-р барааг $3$ доллараар авч сэтгэл ханамжаа $5$-аар нэмэгдүүлж чадна.
  2. Цаг $2$ болж байхад $1$-р, $2$-р, $3$-р бараанууд боломжтой байна. Би $1$-р барааг $2$ доллараар, $2$-р барааг $3$ доллараар авч сэтгэл ханамжаа $3+5=8$-аар нэмэгдүүлж чадна.
  3. Цаг $2$ болж байхад $1$-р, $2$-р, $3$-р бараанууд боломжтой байна. Би $1$-р барааг $2$ доллараар, $3$-р барааг $4$ доллараар авч сэтгэл ханамжаа $3+7=10$-аар нэмэгдүүлж чадна.
  4. Цаг $5$ болж байхад $1$-р, $3$-р, $4$-р бараанууд боломжтой байна. Би $1$-р барааг $2$ доллараар, $4$-р барааг $11$ доллараар авч сэтгэл ханамжаа $3+15=18$-аар нэмэгдүүлж чадна. Энэ тохиолдолд би бүх төсвөө зарцуулах шаардлагагүй болохыг анзаараарай.
Сэтгэгдлүүдийг ачааллаж байна...