Most Dangerous Shark
Contest: Codeforces Round 541 (Div. 2)
Difficulty rating: 2700
Tags: data structures, dp, two pointers

Semyon participates in the most prestigious competition of the world ocean for the title of the most dangerous shark. During this competition sharks compete in different subjects: speed swimming, masking, map navigation and many others. Now Semyon is taking part in «destruction» contest.

During it, $$$m$$$ dominoes are placed in front of the shark. All dominoes are on the same line, but the height of the dominoes may vary. The distance between adjacent dominoes is $$$1$$$. Moreover, each Domino has its own cost value, expressed as an integer. The goal is to drop all the dominoes. To do this, the shark can push any domino to the left or to the right, and it will begin falling in this direction. If during the fall the domino touches other dominoes, they will also start falling in the same direction in which the original domino is falling, thus beginning a chain reaction, as a result of which many dominoes can fall. A falling domino touches another one, if and only if the distance between them was strictly less than the height of the falling domino, the dominoes do not necessarily have to be adjacent.

Of course, any shark can easily drop all the dominoes in this way, so the goal is not to drop all the dominoes, but do it with a minimum cost. The cost of the destruction is the sum of the costs of dominoes that the shark needs to push to make all the dominoes fall.

Simon has already won in the previous subjects, but is not smart enough to win in this one. Help Semyon and determine the minimum total cost of the dominoes he will have to push to make all the dominoes fall.

Input format:
In order to reduce input size, the heights and costs of the dominoes are described with blocks.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 250\,000, 1 \leq m \leq 10^7$$$) — the number of the blocks and the total number of the dominoes Semyon must drop.

Then descriptions of $$$n$$$ blocks follow. Description of every block consists of three lines.

The first line of block's description contains a single integer $$$k_i$$$ ($$$1 \leq k_i \leq 250\,000, \sum_{i = 1}^{n}{k_i} \leq 250\,000$$$) — the number of dominoes in the block.

The second line of block's description contains $$$k_i$$$ integers $$$a_j$$$ ($$$1 \leq a_j \leq m$$$) — the heights of the dominoes in the blocks.

The third line contains $$$k_i$$$ integers $$$c_j$$$ ($$$1 \leq c_j \leq 100\,000$$$) — the costs of the dominoes in the block.

Then the domino sequence is described (from left to right).

The first line of this description contains a single integer $$$q$$$ ($$$n \leq q \leq 250\,000$$$) — the number of blocks in the sequence of domino sequence.

Each of the following $$$q$$$ lines contains integers $$$id_i, mul_i$$$ ($$$1 \leq id_i \leq n$$$, $$$1 \leq mul_i \leq 100\,000$$$), denoting that the next $$$k_{id_i}$$$ dominoes are dominoes of the block $$$id_i$$$, with their cost multiplied by $$$mul_i$$$.

It's guaranteed, that $$$\sum_{i = 1}^{q}{k_{id_i}} = m$$$, and that's every block is used in the sequence at least once.

Output format:
Print exactly one integer — the minimum cost to make all the dominoes fall.

Constraints:
Time limit: 2.0 s
Memory limit: 768.0 MB

Note:
In the first example, there are $$$7$$$ dominoes in front of the Semyon. Their heights are equal to $$$[3, 1, 2, 2, 1, 2, 2]$$$, and their costs are equal to $$$[4, 3, 6, 3, 1, 2, 1]$$$. Semyon should drop the domino with index $$$7$$$ to the left, it will fall and drop the domino $$$6$$$ as well. The domino $$$6$$$ during the fall will drop the domino $$$5$$$, however the latter will not drop any more dominoes. Then Semyon should drop domino with number $$$1$$$ to the right and it will drop dominoes $$$2$$$ and $$$3$$$ after falling. And the domino $$$3$$$ will drop the domino $$$4$$$ after falling. Hence all dominoes are fallen this way.

In the second example, there is a single domino of cost $$$10000000000$$$.

Example input:
2 7
3
1 2 2
1 2 1
1
3
2
3
2 2
1 3
1 1

Example output:
5

Example input:
1 1
1
1
100000
1
1 100000

Example output:
10000000000

Editorial:
This problem can be solved using dynamic programming technique.
Let $$$dp_i$$$ be minimum cost to fall first $$$i$$$ dominoes. If $$$i$$$-th domino was dropped to the right $$$dp_i = min(dp_j + c_i)$$$ over such $$$j$$$ that dropped $$$i$$$-th domino will fall all dominoes from $$$j + 1$$$ to $$$i$$$. Otherwise, some other domino was dropped to the right and fell domino $$$i$$$. Then $$$dp_i = min(dp_{j - 1} + c_j)$$$ other such $$$j$$$, that $$$j$$$-th domino dropped to the right will fall $$$i$$$-th domino. Such solution works in $$$O(m^2)$$$.
We need to speed up this solution. We need to find possible $$$j$$$ for each $$$i$$$ faster. At first let's notice, that possible $$$j$$$'s forms subsegments, so we need just find most right $$$j$$$. This can be done using stack technique like finding nearest element greater than current.
Another part of the solution, we need to optimize is taking range minimum query of $$$dp$$$'s. That can be easily done using segment tree technique or fenwick tree technique, however it requires $$$O(log m)$$$ time per query which is too slow. To make it faster we can use stack technique again! Let's maintain stack of increasing values of $$$dp_i$$$ (or $$$dp_i + c_i$$$, depending on case). Because segments on which we are taking minimum are nested or non-intersecting we can always drop all values after the optimum for each query. Using amortized analysis technique, we can see that such solution works in $$$O(m)$$$.