Акула Семён участвует в самом престижном соревновании Мирового океана на звание самой опасной акулы. Во время этого состязания акулы соревнуются в различных дисциплинах: плавание на скорость, маскировка, навигация по картам и многим другим. Сейчас Семён проходит испытание под названием «разрушение».
Во время этого испытания перед акулой ставят \(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\), а также, что каждый блок встречается хотя бы один раз в последовательности доминошек, которые требуется уронить.
Выходные данные
Выведите одно целое число — минимальную суммарную стоимость доминошек, которые надо толкнуть, чтобы все доминошки упали.
Примечание
В первом примере перед Семёном стоят \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 7
3
1 2 2
1 2 1
1
3
2
3
2 2
1 3
1 1
|
5
|
|
2
|
1 1
1
1
100000
1
1 100000
|
10000000000
|