谢苗参加了世界海洋上最负盛名的比赛,争夺最危险鲨鱼的称号。在这场比赛中,鲨鱼们将参加不同的比赛项目:速度游泳、掩蔽、地图导航等等。现在谢苗正在参加“毁灭”比赛。
在此期间,$$$m$$$ 多米诺骨牌被放置在鲨鱼面前。所有多米诺骨牌都在同一条线上,但多米诺骨牌的高度可能有所不同。相邻多米诺骨牌之间的距离为 $$$1$$$。此外,每个多米诺骨牌都有自己的成本值,以整数表示。目标是推倒所有的多米诺骨牌。为此,鲨鱼可以将任何多米诺骨牌推向左侧或右侧,然后它就会开始朝这个方向下落。如果在倒下过程中多米诺骨牌接触到其他多米诺骨牌,它们也会开始沿着原来的多米诺骨牌倒下的相同方向倒下,从而开始连锁反应,结果许多多米诺骨牌会倒下。一张倒下的多米诺骨牌会碰到另一张多米诺骨牌,当且仅当它们之间的距离严格小于倒下的多米诺骨牌的高度时,多米诺骨牌不一定是相邻的。
当然,任何鲨鱼都可以通过这种方式轻松掉落所有多米诺骨牌,因此目标不是掉落所有多米诺骨牌,而是以最小的成本做到这一点。破坏的成本是鲨鱼需要推动多米诺骨牌才能使所有多米诺骨牌倒下的成本总和。
西蒙已经在前几科中获胜,但在这一科中还不够聪明,无法获胜。帮助 Semyon 并确定他必须推动的多米诺骨牌的最小总成本才能使所有多米诺骨牌倒下。
输入
为了减少输入大小,多米诺骨牌的高度和成本用块来描述。
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 250\,000, 1 \leq m \leq 10^7$$$) — Semyon 必须掉落的方块数量和多米诺骨牌总数。
然后是 $$$n$$$ 块的描述。每个块的描述由三行组成。
块描述的第一行包含一个整数 $$$k_i$$$ ($$$1 \leq k_i \leq 250\,000, \sum_{i = 1}^{n}{k_i} \leq 250\,000$$$) — 块中多米诺骨牌的数量。
块描述的第二行包含 $$$k_i$$$ 整数 $$$a_j$$$ ($$$1 \leq a_j \leq m$$$) — 块中多米诺骨牌的高度。
第三行包含 $$$k_i$$$ 整数 $$$c_j$$$ ($$$1 \leq c_j \leq 100\,000$$$) — 块中多米诺骨牌的成本。
然后描述多米诺骨牌序列(从左到右)。
该描述的第一行包含一个整数 $$$q$$$ ($$$n \leq q \leq 250\,000$$$) — 多米诺骨牌序列中的块数。
下面的每一行 $$$q$$$ 都包含整数 $$$id_i, mul_i$$$ ($$$1 \leq id_i \leq n$$$, $$$1 \leq mul_i \leq 100\,000$$$),表示接下来的 $$$k_{id_i}$$$ 多米诺骨牌是块$$$id_i$$$,其成本乘以$$$mul_i$$$。
可以保证 $$$\sum_{i = 1}^{q}{k_{id_i}} = m$$$,并且每个块在序列中至少使用一次。
输出
精确打印一个整数——使所有多米诺骨牌倒下的最小成本。
示例
输入 #1
2 7 3 1 2 2 1 2 1 1 3 2 3 2 2 1 3 1 1
输出 #1
5
输入 #2
1 1 1 1 100000 1 1 100000
输出 #2
10000000000
注意
在第一个示例中,Semyon 前面有 $$$7$$$ 多米诺骨牌。它们的高度等于 $$$[3, 1, 2, 2, 1, 2, 2]$$$,它们的成本等于 $$$[4, 3, 6, 3, 1, 2, 1]$$$。 Semyon 应该将索引为 $$$7$$$ 的多米诺骨牌扔到左侧,它会倒下并同时掉落多米诺骨牌 $$$6$$$。秋季期间的多米诺骨牌 $$$6$$$ 会掉落多米诺骨牌 $$$5$$$,但后者不会再掉落更多的多米诺骨牌。然后 Semyon 应该将编号为 $$$1$$$ 的多米诺骨牌扔到右侧,掉落后会掉落多米诺骨牌 $$$2$$$ 和 $$$3$$$ 。多米诺骨牌 $$$3$$$ 掉落后会掉落多米诺骨牌 $$$4$$$。因此,所有的多米诺骨牌都是这样倒下的。
在第二个示例中,有一个成本为 $$$10000000000$$$ 的多米诺骨牌。