题目背景

这是一道好吃的题目。

题目描述

有一条小吃街，从左到右依次排列着 $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$ 个吃货的参数。

输出格式

对于每个吃货，输出一行一个整数，表示最大的美味度和。

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

提示

【样例输入输出解释】

样例 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$。