Description

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.

Input Format

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.

Output Format

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

8 5
10 31 36 30 36 24 29 29
59 152 284 202 282 156 277 212
3 5 81
4 5 75
7 8 71
1 3 92
4 4 95

566
484
489
495
202

15 10
5 15 18 15 18 12 14 14 10 15 17 18 9 7 6 
11 31 26 34 19 17 15 25 11 34 18 26 21 8 11 
7 15 31
2 9 67
8 15 77
3 13 43
6 7 98
2 2 110
3 13 26
11 11 84
7 14 25
4 6 90

66
118
128
89
32
31
55
18
55
70

Hint

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