{"raw_statement":[{"iden":"background","content":"小挖喜欢买花，但是 ta 太懒了！所以这个任务全权交给了你。"},{"iden":"statement","content":"花店里只有 $n$ 株花，每一株花都有三个属性：价格 $cost_i$、美丽度 $be_i$、新鲜程度 $fr_i$。\n\n小挖每次都有不同的要求。准确来说，对于第 $j$ 次买花，你手里的钱**至多能买下总价为 $c_j$ 的花**。同时，小挖还要求购买花的**新鲜程度总和大于等于 $f_j$**。而小挖希望知道，在满足 ta 给出的条件后，购买**花的美丽度总和**的最大值是多少？如果拥有的钱无论如何都无法满足新鲜程度总和大于等于 $f_j$ 的要求，输出 $0$。\n\n\n小挖一共要让你买 $q$ 次花，你能否正确回答 ta 的问题呢？询问彼此独立。"},{"iden":"input","content":"第 $1$ 行，共两个正整数 $n,q$。\n\n第 $2\\sim n+1$ 行，每行三个正整数 $cost_i,fr_i,be_i$，分别表示一株花的三个属性。\n\n第 $n+2\\sim n+q+1$ 行，每行两个正整数 $c_j,f_j$，表示每次买花时的要求。"},{"iden":"output","content":"共 $q$ 行，每行一个整数，表示美丽度总和的最大值。如果无解，输出 $0$。"},{"iden":"note","content":"对于 $20\\%$ 的数据，$3\\leq n,q\\leq 16$。\n\n对于 $40\\%$ 的数据，$3\\leq n,q\\leq 30$，$0\\leq c_j,f_j\\leq 50$。\n\n对于 $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$。\n\n对于另外 $20\\%$ 的数据，对于每次买花，都有 $f_j=0$。\n\n对于 $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$。"}],"translated_statement":null,"sample_group":[["5 1\n2 4 5\n4 3 3\n1 3 2\n3 4 3\n3 2 5\n10 10\n","15\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}