You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

小挖喜欢买花，但是 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$。

5 1
2 4 5
4 3 3
1 3 2
3 4 3
3 2 5
10 10

15

提示

对于 $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$。