大样例下载

题目描述

有 $n$ 个物品，编号为 $1$ 至 $n$。

第 $i$ 个物品的体积为 $w_i$，价值为 $v_i$。

有 $q$ 次询问，每次询问形如 $L_i,R_i,W_i$。

对于每次询问，你需要回答以下问题

从编号 $L_i$ 到 $R_i$ 的物品中选择若干物品放进容量为 $W_i$ 的背包里，每个物品最多只能放一次。能装的价值最大是多少？

输入格式

第一行两个整数 $n,q$ 。

第二行 $n$ 个整数，表示 $w$。

第三行 $n$ 个整数，表示 $v$。

接下来 $q$ 行，每行三个整数 $L_i,R_i,W_i$，表示一次询问。

输出格式

每个询问输出一个整数，表示答案。

每个数占一行。

样例

input

5 3
1 2 3 4 5
1 2 3 4 5
1 2 3
2 4 4
2 4 8

output

3
4
7

样例解释

询问 1： 可以选取第一个，第二个物品，所占体积为 $3$，价值为 $3$。

询问 2： 可以选取第四个物品，所占体积为 $4$，价值为 $4$。

询问 3： 可以选取第三个，第四个物品，所占体积为 $7$，价值为 $7$。背包不必放满。但是不能放 $4$ 个第二个物品，因为 一次询问中，每个物品只能拿一次。但不同的询问之间互不干扰，比如询问 2 和询问 3 都可以拿第四个物品。

可以证明，这是最优方法。

数据范围

对于前 $20\%$ 的数据，$1 \le n,q \le 100, 1 \le W_i ,w_i,v_i \le 50$。

对于前 $50\%$ 的数据，$1 \le n,q \le 10^5, 1 \le W_i ,w_i,v_i \le 50$。

对于 $100\%$ 的数据，$1 \le n,q \le 5 \times 10^5, 1 \le W_i ,w_i,v_i \le 50,1 \le L_i,R_i \le n ,\sum _{i=1} ^{n-1} (\mid L_{i+1} -L_i \mid + \mid R_{i+1} -R_i \mid) \le 10^6$。