题目背景

本题已经增加 hack 数据。hack 数据位于 subtask 7，记 0 分。此外本题时限较大数据点较多，希望各位不要滥用评测资源。

你正在打块，突然家长走了进来，于是你假装在玩原神。

题目描述

你改造了原神的抽卡系统。

具体而言，在第 $i$ 次抽卡时，系统将会给出一个可重集合 $S_i$，表示这次抽卡中可供选择的角色。第 $j$ 个角色有两个属性：力量值 $s_{i,j}$ 与魔力值 $m_{i,j}$。你可以从中选择一名角色，并将其加入到自己的背包中；当然，你也可以不做任何选择。你的力量值被定义为背包中所有角色的力量值之和，同时你需要时刻保证背包中角色的魔力值之积不超过魔力上限 $v$。你的任务是最大化自己的力量值。

但是，你很快就厌烦了千篇一律的抽卡。为了给生活找点乐子，你想到了这样的问题：如果游戏从第 $l$ 次抽卡开始，到第 $r$ 次抽卡结束，你的力量值最大是多少呢？

你一口气提出了 $q$ 个这样的问题。现在，你需要计算出它们的答案。

形式化题意：

给出一个长为 $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,v$。

接下来 $n$ 行，每行首先读入 $|S_i|$，接下来读入 $|S_i|$ 对正整数 $(s_{i,j},m_{i,j})$，即 $S_i$ 中每一角色的力量值与魔力值。

随后一行，读入一个正整数 $q$。

接下来 $q$ 行，每行两个正整数 $l,r$，表示一次询问。注意询问间两两独立，即每次询问都将被视作一次新的游戏。

输出格式

输出共 $q$ 行。对于每次询问，输出你的体力值的最大值。

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

3
8
13
11
6

提示

样例解释

对于第一组询问，最优策略是从 $S_3$ 中选择 $(3,3)$。此时你的能力值为 $3$。

对于第三组询问，最优策略是从 $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$。

数据范围与约定

本题使用子任务捆绑测试，只有通过子任务内全部测试点才可以获得该子任务的相应分数。

记 $tot=\sum_{i=1}^n|S_i|$。

• 子任务 1（5 分）：保证 $n,tot\le 10$。
• 子任务 2（20 分）：保证 $n,v,tot,q\le 100$。
• 子任务 3（15 分）：保证所有 $m_{i,j}$ 在范围内均匀随机生成。
• 子任务 4（20 分）：保证 $1\le n,v,tot,q\le 10^4$。
• 子任务 5（15 分）：保证对于所有询问，均有 $l=1$ 或者 $r=n$。
• 子任务 6（25 分）：无特殊限制。

对于所有数据，保证 $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$。