题目背景

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

题目描述

花店里只有 $n$ 株花，每一株花都有三个属性：价格 $cost_i$、美丽度 $be_i$、新鲜程度 $fr_i$。

小挖每次都有不同的要求。准确来说，对于第 $j$ 次买花，你手里的钱至多能买下总价为 $c_j$ 的花。同时，小挖还要求购买花的新鲜程度总和大于等于 $f_j$。而小挖希望知道，在满足 ta 给出的条件后，购买花的美丽度总和的最大值是多少？

小挖一共要让你买 $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$ 行，每行一个整数，表示美丽度总和的最大值。

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