区间背包

题目描述

有$n$件物品，第$i$件物品的体积是$h_{i}$，价值是$w_{i}$。

有$m$组询问，每组询问给定$l_{i}$，$r_{i}$，$t_{i}$，表示仅考虑$[l_{i}$，$r_{i}]$的物品，且背包容量仅有$t_{i}$，问能得到的最大价值。

需要注意，每个物品仅有一个。

输入格式

第一行为两个整数，分别表示$n$，$m$。

第二行为$n$个整数，第$i$个整数表示$h_{i}$。

第三行为$n$个整数，第$i$个整数表示$w_{i}$。

第$4$到第$(m+3)$行，每行三个整数，第$(i+3)$行的整数$l_{i}$，$r_{i}$，$t_{i}$分别表示第$i$组询问的参数。

输出格式

对于每组询问，输出一行一个整数，表示最大的价值和。

数据范围与提示

• 对于$30\%$的数据，$n$，$m \leq 500$；
• 对于$60\%$的数据，$n \leq 4 \times 10^{4}$，$m \leq 5000$；
• 对于$100\%$的数据，$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}$。

样例

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

说明

对于第一组数据的第一组询问，可以选择第$3$个物品和第$5$个物品。

容量和为$36+36=72<81$，价值和为$284+282=566$。

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

说明

对于第二组数据的第一个询问，可以选择第$10$，第$13$，第$15$个物品。

容量和为$15+9+6=30 \leq 31$，价值和为$34+21+11=66$。