G. Самая опасная акула
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
768 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Акула Семён участвует в самом престижном соревновании Мирового океана на звание самой опасной акулы. Во время этого состязания акулы соревнуются в различных дисциплинах: плавание на скорость, маскировка, навигация по картам и многим другим. Сейчас Семён проходит испытание под названием «разрушение».

Во время этого испытания перед акулой ставят $$$m$$$ доминошек. Все доминошки стоят на одной прямой, однако высоты доминошек могут различаться. Расстояние между соседними доминошками равно $$$1$$$. Кроме того, у каждой доминошки есть своя стоимость, выраженная целым числом. Цель акулы — уронить все доминошки. Для этого акула может толкнуть любую доминошку влево или вправо, после чего она начнёт падать в этом направлении. Если во время падения доминошка задевает другие, они также начинают падать в ту же сторону, в которую падала исходная, таким образом начинается цепная реакция, в результате которой может упасть много доминошек. Падающая доминошка задевает другую, если и только если расстояние между ними строго меньше высоты падающей доминошки, причём доминошки не обязательно должны быть соседними.

Разумеется, любая акула справится с тем, чтобы уронить все доминошки таким образом, поэтому оценивается не факт разрушения, а его стоимость. Стоимостью разрушения называется сумма стоимостей доминошек, которые акуле придётся толкнуть, чтобы все доминошки упали.

Семён уже победил в прошлых испытаниях, однако недостаточно умён, чтобы победить в этом. Помогите Семёну и определите минимальную суммарную стоимость доминошек, которые ему придётся толкнуть, чтобы все доминошки упали.

Входные данные

Для уменьшения размера ввода высоты и стоимости доминошек задаются при помощи блоков.

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 250\,000, 1 \leq m \leq 10^7$$$) — количество блоков и суммарное количество доминошек, которые надо уронить Семёну.

Затем следует описание $$$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$$$, а также, что каждый блок встречается хотя бы один раз в последовательности доминошек, которые требуется уронить.

Выходные данные

Выведите одно целое число — минимальную суммарную стоимость доминошек, которые надо толкнуть, чтобы все доминошки упали.

Примеры
Входные данные
2 7
3
1 2 2
1 2 1
1
3
2
3
2 2
1 3
1 1
Выходные данные
5
Входные данные
1 1
1
1
100000
1
1 100000
Выходные данные
10000000000
Примечание

В первом примере перед Семёном стоят $$$7$$$ доминошек. Их высоты равны $$$[3, 1, 2, 2, 1, 2, 2]$$$, а стоимости равны $$$[4, 3, 6, 3, 1, 2, 1]$$$. Сначала Семёну следует уронить доминошку с номером $$$7$$$ влево, она упадёт и заденет доминошку с номером $$$6$$$. Доминошка $$$6$$$, падая, заденет доминошку с номером $$$5$$$, которая упадёт, но не заденет другие доминошки. Затем Семён должен уронить доминошку с номером $$$1$$$ вправо, она, падая, заденет доминошки с номерами $$$2$$$ и $$$3$$$, а доминошка $$$3$$$, падая, заденет доминошку $$$4$$$, таким образом все доминошки упадут.

Во втором примере перед Семёном стоит одна доминошка стоимостью $$$10000000000$$$.