P6240 Delicious Problem

This is a delicious problem.

There is a snack street with $n$ shops arranged from left to right, numbered starting from $1$. Shop $i$ sells only one kind of snack, with calories $h_i$ and tastiness $w_i$. Now there are $m$ food lovers coming to the street. Food lover $i$ will look for snacks among shops in $[l_i, r_i]$, and to avoid gaining too much weight, they can consume at most $t_i$ calories. Eating too many snacks can get boring, so the snack from the same shop can be eaten at most once. Each food lover wants to know the maximum total tastiness they can get.

The first line contains two integers, representing $n$ and $m$. The second line contains $n$ integers; the $i$-th integer is $h_i$. The third line contains $n$ integers; the $i$-th integer is $w_i$. Lines $4$ to $(m + 3)$ each contain three integers. In line $(i + 3)$, the integers $l_i$, $r_i$, and $t_i$ represent the parameters of the $i$-th food lover.

For each food lover, output one integer per line, representing the maximum sum of tastiness.

#### Sample Input/Output Explanation **Sample 1 Explanation** For the first food lover in the first set of testdata, they can choose shop $3$ and shop $5$. The consumed calories are $36+36=72\leq 81$, and the obtained tastiness is $284+282=566$. **Sample 2 Explanation** For the first food lover in the second set of testdata, they can choose shops $10$, $13$, and $15$. The consumed calories are $15+9+6=30\leq 31$, and the obtained tastiness is $34+21+11=66$. --- #### Constraints - For $30\%$ of the testdata, $n,m\leq 500$. - For $60\%$ of the testdata, $n\leq 4\times 10^4$, $m\leq 5000$. - For $100\%$ of the testdata, $1 \leq n\leq 4\times 10^4$, $1 \leq m\leq 2\times 10^5$, $1\leq l_i\leq r_i\leq n$, $1\leq h_i,t_i\leq 200$, $1\leq w_i\leq 10^7$. Translated by ChatGPT 5