#P6240. 好吃的题目

好吃的题目

题目背景

这是一道好吃的题目。

题目描述

有一条小吃街,从左到右依次排列着 nn 个商店,从 11 开始标号。

ii 个商店会只出售一种小吃,热量为 hih_i,美味度为 wiw_i

现在有 mm 个吃货要来逛街,第 ii 个吃货会在 [li,ri][l_i,r_i] 的商店内寻找小吃,而且为了防止太胖,最多能摄入 tit_i 的热量。

小吃吃多了会腻,所以同一个商店的小吃只能吃一次。

现在每个吃货想知道自己最多能得到多少美味度。

输入格式

第一行为两个整数,分别表示 n,mn,m

第二行为 nn 个整数,第 ii 个整数表示 hih_i

第三行为 nn 个整数,第 ii 个整数表示 wiw_i

44 到第 (m+3)(m + 3) 行,每行三个整数,第 (i+3)(i + 3) 行的整数 li,ri,til_i, r_i, t_i 分别表示第 ii 个吃货的参数。

输出格式

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

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 解释

对于第一组数据的第一个吃货,可以选择第 33 个商店和第 55 个商店。

摄入的热量为 36+36=728136+36=72\leq 81,获得美味度为 284+282=566284+282=566

样例 2 解释

对于第二组数据的第一个吃货,可以选择第 1010,第 1313,第 1515 个商店。

摄入的热量为 15+9+6=303115+9+6=30\leq 31,获得美味度为 34+21+11=6634+21+11=66


【数据规模与约定】

  • 对于 30%30\% 的数据,满足 n,m500n,m\leq 500
  • 对于 60%60\% 的数据,满足 n4×104n\leq 4\times 10^4m5000m\leq 5000
  • 对于 100%100\% 的数据,满足 1n4×1041 \leq n\leq 4\times 10^41m2×1051 \leq m\leq 2\times 10^51lirin1\leq l_i\leq r_i\leq n1hi,ti2001\leq h_i,t_i\leq 2001wi1071\leq w_i\leq 10^7