{"problem":{"name":"小挖的买花","description":{"content":"花店里只有 $n$ 株花，每一株花都有三个属性：价格 $cost_i$、美丽度 $be_i$、新鲜程度 $fr_i$。 小挖每次都有不同的要求。准确来说，对于第 $j$ 次买花，你手里的钱**至多能买下总价为 $c_j$ 的花**。同时，小挖还要求购买花的**新鲜程度总和大于等于 $f_j$**。而小挖希望知道，在满足 ta 给出的条件后，购买**花的美丽度总和**的最大值是多少？如果拥有的钱无","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8548"},"statements":[{"statement_type":"Markdown","content":"花店里只有 $n$ 株花，每一株花都有三个属性：价格 $cost_i$、美丽度 $be_i$、新鲜程度 $fr_i$。\n\n小挖每次都有不同的要求。准确来说，对于第 $j$ 次买花，你手里的钱**至多能买下总价为 $c_j$ 的花**。同时，小挖还要求购买花的**新鲜程度总和大于等于 $f_j$**。而小挖希望知道，在满足 ta 给出的条件后，购买**花的美丽度总和**的最大值是多少？如果拥有的钱无论如何都无法满足新鲜程度总和大于等于 $f_j$ 的要求，输出 $0$。\n\n小挖一共要让你买 $q$ 次花，你能否正确回答 ta 的问题呢？询问彼此独立。\n\n## Input\n\n第 $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$，表示每次买花时的要求。\n\n## Output\n\n共 $q$ 行，每行一个整数，表示美丽度总和的最大值。如果无解，输出 $0$。\n\n[samples]\n\n## Background\n\n小挖喜欢买花，但是 ta 太懒了！所以这个任务全权交给了你。\n\n## Note\n\n对于 $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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8548","tags":["动态规划 DP","背包 DP"],"sample_group":[["5 1\n2 4 5\n4 3 3\n1 3 2\n3 4 3\n3 2 5\n10 10\n","15\n"]],"created_at":"2026-03-03 11:09:25"}}