{"problem":{"name":"游戏王","description":{"content":"你改造了原神的抽卡系统。 具体而言，在第 $i$ 次抽卡时，系统将会给出一个可重集合 $S_i$，表示这次抽卡中可供选择的角色。第 $j$ 个角色有两个属性：力量值 $s_{i,j}$ 与魔力值 $m_{i,j}$。你可以从中选择一名角色，并将其加入到自己的背包中；当然，你也可以不做任何选择。你的力量值被定义为背包中所有角色的力量值之和，同时你需要时刻保证背包中角色的魔力值之积不超过魔力上限 $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9818"},"statements":[{"statement_type":"Markdown","content":"你改造了原神的抽卡系统。\n\n具体而言，在第 $i$ 次抽卡时，系统将会给出一个可重集合 $S_i$，表示这次抽卡中可供选择的角色。第 $j$ 个角色有两个属性：力量值 $s_{i,j}$ 与魔力值 $m_{i,j}$。你可以从中选择一名角色，并将其加入到自己的背包中；当然，你也可以不做任何选择。你的力量值被定义为背包中所有角色的力量值之和，同时你需要时刻保证背包中角色的魔力值之积不超过魔力上限 $v$。你的任务是最大化自己的力量值。\n\n但是，你很快就厌烦了千篇一律的抽卡。为了给生活找点乐子，你想到了这样的问题：如果游戏从第 $l$ 次抽卡开始，到第 $r$ 次抽卡结束，你的力量值最大是多少呢？\n\n你一口气提出了 $q$ 个这样的问题。现在，你需要计算出它们的答案。\n\n**形式化题意**：\n\n给出一个长为 $n$ 的序列 $\\{S_n\\}$，其中 $S_i$ 为多个二元组 $(s_{i,j},m_{i,j})$ 构成的可重集。有 $q$ 次询问，每次给定 $l,r$，你需要从 $S_l,S_{l+1},\\cdots,S_r$ 的每个集合中分别选出 $0$ 个或 $1$ 个二元组。记选出的 $k$ 个二元组为 $(s'_i,m'_i),1\\le i\\le k$，则你需要在保证 $\\prod_{i=1}^km'_i\\le v$ 的基础上，最大化 $\\sum_{i=1}^k s'_i$。\n\n## Input\n\n输入的第一行包含两个正整数 $n,v$。\n\n接下来 $n$ 行，每行首先读入 $|S_i|$，接下来读入 $|S_i|$ 对正整数 $(s_{i,j},m_{i,j})$，即 $S_i$ 中每一角色的力量值与魔力值。\n\n随后一行，读入一个正整数 $q$。\n\n接下来 $q$ 行，每行两个正整数 $l,r$，表示一次询问。**注意询问间两两独立，即每次询问都将被视作一次新的游戏。**\n\n## Output\n\n输出共 $q$ 行。对于每次询问，输出你的体力值的最大值。\n\n[samples]\n\n## Background\n\n**本题已经增加 hack 数据**。hack 数据位于 subtask 7，记 0 分。此外本题时限较大数据点较多，希望各位不要滥用评测资源。\n\n你正在打块，突然家长走了进来，于是你假装在玩原神。\n\n## Note\n\n#### 样例解释\n\n对于第一组询问，最优策略是从 $S_3$ 中选择 $(3,3)$。此时你的能力值为 $3$。\n\n对于第三组询问，最优策略是从 $S_1$ 中选择 $(2,1)$，$S_2$ 中选择 $(5,3)$，$S_3$ 中选择 $(3,3)$，$S_4$ 中选择 $(3,1)$，此时魔力值之积等于 $1\\times 3\\times 3\\times 1=9\\le 10$，你的能力值等于 $2+5+3+3=13$。 \n\n#### 数据范围与约定\n\n**本题使用子任务捆绑测试，只有通过子任务内全部测试点才可以获得该子任务的相应分数**。\n\n记 $tot=\\sum_{i=1}^n|S_i|$。\n\n- 子任务 1（5 分）：保证 $n,tot\\le 10$。\n- 子任务 2（20 分）：保证 $n,v,tot,q\\le 100$。\n- 子任务 3（15 分）：保证所有 $m_{i,j}$ 在范围内均匀随机生成。\n- 子任务 4（20 分）：保证 $1\\le n,v,tot,q\\le 10^4$。\n- 子任务 5（15 分）：保证对于所有询问，均有 $l=1$ 或者 $r=n$。\n- 子任务 6（25 分）：无特殊限制。\n\n对于所有数据，保证 $1\\le n,tot\\le 10^5$，$1\\le q\\le 2\\times 10^5$，$1\\le m_{i,j}\\le v\\le 10^5$，$1\\le s_{i,j}\\le 10^4$，$1\\le l\\le r\\le n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9818","tags":["O2优化"],"sample_group":[["4 10\n2 2 1 5 9\n1 5 3\n3 2 1 2 1 3 3\n1 3 1\n5\n3 3\n2 3\n1 4\n2 4\n3 4","3\n8\n13\n11\n6"]],"created_at":"2026-03-03 11:09:25"}}