好吃的题目
题目背景
这是一道好吃的题目。
题目描述
有一条小吃街,从左到右依次排列着 $n$ 个商店,从 $1$ 开始标号。
第 $i$ 个商店会只出售一种小吃,热量为 $h_i$,美味度为 $w_i$。
现在有 $m$ 个吃货要来逛街,第 $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$ 个吃货的参数。
输出格式
对于每个吃货,输出一行一个整数,表示最大的美味度和。
输入输出样例
输入样例 #1
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
输出样例 #1
566
484
489
495
202
输入样例 #2
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
输出样例 #2
66
118
128
89
32
31
55
18
55
70
说明
#### 【样例输入输出解释】
**样例 1 解释**
对于第一组数据的第一个吃货,可以选择第 $3$ 个商店和第 $5$ 个商店。
摄入的热量为 $36+36=72\leq 81$,获得美味度为 $284+282=566$。
**样例 2 解释**
对于第二组数据的第一个吃货,可以选择第 $10$,第 $13$,第 $15$ 个商店。
摄入的热量为 $15+9+6=30\leq 31$,获得美味度为 $34+21+11=66$。
---
#### 【数据规模与约定】
- 对于 $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$。