Background

This problem has already added hack testdata. The hack testdata is in subtask 7 and is worth 0 points. Also, this problem has a large time limit and many test points, so please do not abuse judging resources.

You are playing Minecraft, and suddenly your parents walk in, so you pretend you are playing Genshin Impact.

Problem Description

You modified Genshin Impact’s gacha system.

Specifically, on the $i$-th pull, the system gives a multiset $S_i$, which represents the characters available to choose from in this pull. The $j$-th character has two attributes: strength value $s_{i,j}$ and magic value $m_{i,j}$. You may choose one character from it and put it into your backpack; of course, you may also choose nothing. Your strength value is defined as the sum of the strength values of all characters in the backpack, and you must always ensure that the product of the magic values of the characters in the backpack does not exceed the magic limit $v$. Your task is to maximize your strength value.

However, you soon get tired of the repetitive gacha. To make life a bit more fun, you think of the following question: if the game starts from the $l$-th pull and ends at the $r$-th pull, what is the maximum strength value you can get?

You ask $q$ such questions in a row. Now you need to compute the answers to them.

Formal statement:

Given a sequence $\{S_n\}$ of length $n$, where $S_i$ is a multiset consisting of multiple pairs $(s_{i,j},m_{i,j})$. There are $q$ queries. Each query gives $l,r$. You need to choose $0$ or $1$ pair from each of $S_l,S_{l+1},\cdots,S_r$. Suppose the $k$ chosen pairs are $(s'_i,m'_i),1\le i\le k$. Then, under the constraint $\prod_{i=1}^k m'_i\le v$, you need to maximize $\sum_{i=1}^k s'_i$.

Input Format

The first line contains two positive integers $n,v$.

In the next $n$ lines, each line first reads $|S_i|$, then reads $|S_i|$ pairs of positive integers $(s_{i,j},m_{i,j})$, i.e. the strength value and magic value of each character in $S_i$.

Then one line reads a positive integer $q$.

In the next $q$ lines, each line contains two positive integers $l,r$, representing one query. Note that all queries are independent of each other, i.e. each query is treated as a new game.

Output Format

Output $q$ lines in total. For each query, output the maximum possible value of your strength value.

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

Hint

Explanation of the samples

For the first query, the optimal strategy is to choose $(3,3)$ from $S_3$. At this time, your strength value is $3$.

For the third query, the optimal strategy is to choose $(2,1)$ from $S_1$, $(5,3)$ from $S_2$, $(3,3)$ from $S_3$, and $(3,1)$ from $S_4$. Then the product of magic values equals $1\times 3\times 3\times 1=9\le 10$, and your strength value equals $2+5+3+3=13$.

Constraints and notes

This problem uses bundled subtasks. You can get the score of a subtask only if you pass all test points in that subtask.

Let $tot=\sum_{i=1}^n|S_i|$.

• Subtask 1 (5 points): $n,tot\le 10$.
• Subtask 2 (20 points): $n,v,tot,q\le 100$.
• Subtask 3 (15 points): all $m_{i,j}$ are generated uniformly at random within the range.
• Subtask 4 (20 points): $1\le n,v,tot,q\le 10^4$.
• Subtask 5 (15 points): for all queries, $l=1$ or $r=n$.
• Subtask 6 (25 points): no special constraints.

For all data, it is guaranteed that $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$, and $1\le l\le r\le n$.

Translated by ChatGPT 5