P6240 好吃的题目

这是一道好吃的题目。

有一条小吃街，从左到右依次排列着 $n$ 个商店，从 $1$ 开始标号。 第 $i$ 个商店会只出售一种小吃，热量为 $h_i$，美味度为 $w_i$。 现在有 $m$ 个吃货要来逛街，第 $i$ 个吃货会在 $[l_i,r_i]$ 的商店内寻找小吃，而且为了防止太胖，最多能摄入 $t_i$ 的热量。 小吃吃多了会腻，所以同一个商店的小吃只能吃一次。 现在每个吃货想知道自己最多能得到多少美味度。

无

无

#### 【样例输入输出解释】 **样例 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$。