P8548 小挖的买花

小挖喜欢买花，但是 ta 太懒了！所以这个任务全权交给了你。

花店里只有 $n$ 株花，每一株花都有三个属性：价格 $cost_i$、美丽度 $be_i$、新鲜程度 $fr_i$。 小挖每次都有不同的要求。准确来说，对于第 $j$ 次买花，你手里的钱**至多能买下总价为 $c_j$ 的花**。同时，小挖还要求购买花的**新鲜程度总和大于等于 $f_j$**。而小挖希望知道，在满足 ta 给出的条件后，购买**花的美丽度总和**的最大值是多少？如果拥有的钱无论如何都无法满足新鲜程度总和大于等于 $f_j$ 的要求，输出 $0$。 小挖一共要让你买 $q$ 次花，你能否正确回答 ta 的问题呢？询问彼此独立。

第 $1$ 行，共两个正整数 $n,q$。 第 $2\sim n+1$ 行，每行三个正整数 $cost_i,fr_i,be_i$，分别表示一株花的三个属性。 第 $n+2\sim n+q+1$ 行，每行两个正整数 $c_j,f_j$，表示每次买花时的要求。

共 $q$ 行，每行一个整数，表示美丽度总和的最大值。如果无解，输出 $0$。

对于 $20\%$ 的数据，$3\leq n,q\leq 16$。 对于 $40\%$ 的数据，$3\leq n,q\leq 30$，$0\leq c_j,f_j\leq 50$。 对于 $60\%$ 的数据，$3\leq n\leq 100$，$1\leq q\leq 5\times 10^4$，$0\leq cost_i,fr_i,c_j,f_j\leq 100$。 对于另外 $20\%$ 的数据，对于每次买花，都有 $f_j=0$。 对于 $100\%$ 的数据，$3\leq n\leq 500$，$\boldsymbol{1\leq q\leq 10^6}$，$0\leq cost_i,fr_i,c_j,f_j\leq 500$，$1\leq be_i \leq 10^6$。