Gacha System Optimization

You have modified the gacha (character-drawing) system from Genshin Impact. In this system, on the \(i\)-th draw, a multiset \(S_i\) is provided, containing several characters. Each character is represented by two attributes: strength \(s_{i,j}\) and magic \(m_{i,j}\). From each \(S_i\) you may select at most one character (or you can choose to select none). Your total strength is defined as the sum of the strengths of the selected characters, while you must always ensure that the product of the magic values of the chosen characters does not exceed a given magic limit \(v\).

You will be given \(q\) queries. Each query provides two indices \(l\) and \(r\), meaning that you are allowed to make draws only from sets \(S_l, S_{l+1}, \dots, S_r\). For each query, determine the maximum strength you can achieve while keeping the product of magic values within the limit \(v\).

Formal Problem Statement:

Given a sequence of multisets \(\{S_i\}_{i=1}^{n}\) where each \(S_i\) consists of pairs \((s_{i,j}, m_{i,j})\), and given a magic upper bound \(v\), you are asked to process \(q\) queries. For each query with indices \(l\) and \(r\), you may select from each \(S_i\) (for \(l \le i \le r\)) at most one pair (or none). Let the selected pairs be \((s'_i, m'_i)\) for \(1 \le i \le k\). You must choose the selections such that \[ \prod_{i=1}^{k} m'_i \le v \] while maximizing \[ \sum_{i=1}^{k} s'_i. \]

inputFormat

The first line contains three integers \(n\), \(v\), and \(q\), where \(n\) is the number of draws, \(v\) is the magic limit, and \(q\) is the number of queries.

Then for each \(i = 1, 2, \dots, n\):

• The first line contains an integer \(t_i\) representing the number of characters available in the \(i\)-th draw.
• Then \(t_i\) lines follow, each containing two integers \(s_{i,j}\) and \(m_{i,j}\) denoting the strength and magic values of a character.

After that, \(q\) lines follow, each containing two integers \(l\) and \(r\) representing the range of draws (1-indexed) for the query.

outputFormat

For each query, output a single integer representing the maximum strength achievable while keeping the product of magic values no more than \(v\).

sample

3 10 3
2
5 2
3 3
1
4 1
2
6 2
1 5
1 1
1 2
2 3

5
9
10