Как известно, не только люди любят принимать участие в различных соревнованиях. Среди рыб и моллюсков также проводится множество состязаний на дне океана. Акула Семён участвует в самом престижном соревновании Мирового океана на звание самой опасной акулы. Во время этого состязания акулы соревнуются в различных дисциплинах: плавание на скорость, маскировка, навигация по картам и многим другим. Сейчас Семён проходит испытание под названием «разрушение».
Во время этого испытания перед акулой ставят m доминошек. Все доминошки стоят на одной прямой, однако высоты доминошек могут различаться. Расстояние между соседними доминошками равно 1. Кроме того, у каждой доминошки есть своя стоимость, выраженная целым числом. Цель акулы — уронить все доминошки. Для этого акула может толкнуть любую доминошку влево или вправо, после чего она начнёт падать в этом направлении. Если во время падения доминошка задевает другие, они также начинают падать в ту же сторону, в которую падала исходная, таким образом начинается цепная реакция, в результате которой может упасть множество доминошек. Падающая доминошка задевает другую, если и только если расстояние между ними строго меньше высоты падающей доминошки, причем доминошки не обязательно должны быть соседними.
Разумеется, любая акула справится с тем, чтобы уронить все доминошки таким образом, поэтому оценивается не факт разрушения, а его стоимость. Стоимостью разрушения называется сумма стоимостей доминошек, которые акуле придётся толкнуть, чтобы все доминошки упали.
Семён уже победил в прошлых испытаниях, однако недостаточно умён, чтобы победить в этом. Помогите Семёну и определите, какая минимальная суммарная стоимость доминошек, которые ему придётся толкнуть, чтобы все доминошки упали.
Входные данные
Для уменьшения размера ввода высоты и стоимости доминошек задаются при помощи блоков.
В первой строке заданы два целых числа n и m (1 ≤ n≤ 250 000, 1 ≤ m ≤ 10
7 ) — количество блоков и суммарное количество доминошек, которые надо уронить Семёну, соответственно.
Затем следует описание n блоков. Описание каждого блока состоит из трёх строк.
В первой строке описания блока с номером i содержится целое число k
i (1 ≤ k
i ≤ 250000,
\(\sum_{i=1}^n {k_i ? 250 000}\) ) — количество доминошек в блоке.
Во второй строке описания блока с номером i содержатся ki целых чисел a
i,j (1 ≤ a
i,j ≤ m) — высоты доминошек в блоке.
В третьей строке описания блока с номером i содержатся ki целых чисел c
i,j (1 ≤ c
i,j ≤ 100000) — стоимости доминошек в блоке.
Далее следует описание последовательности доминошек, которые надо уронить Семёну, в порядке слева направо.
В первой строке описания последовательности задано целое число q (n ≤ q ≤ 250000) — количество блоков в последовательности доминошек, которые надо уронить.
В следующих q строках содержатся пары целых чисел id
i mul
i (1 ≤ id
i ≤ n, 1 ≤ mul
i ≤ 100000), обозначающие, что очередные k
idi в порядке слева направо доминошек — это доминошки блока id
i, чьи стоимости были умножены на число mul
i.
Гарантируется, что
\(\sum_{i=1} ^q k_{id_i} = m\) , а также, что каждый блок встречается хотя бы один раз в последовательности доминошек, которые требуется уронить, то есть для всех i от 1 до n найдется j такое, что id
j=i.
Выходные данные
Выведите одно целое число — минимальную суммарную стоимость доминошек, которые надо толкнуть, чтобы все доминошки упали.
Примечание
В первом примере перед Семёном стоят 7 доминошек. Их высоты равны [3122122] , а стоимости равны [4363121] . Сначала Семёну следует уронить доминошку с номером 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 |
Перед Семёном стоят 7 доминошек. Их высоты равны [3122122] , а стоимости равны [4363121] . Сначала Семёну следует уронить доминошку с номером 7 влево, она упадёт и заденет доминошку с номером 6. Доминошка 6, падая, заденет доминошку с номером 5, которая упадёт, но не заденет другие доминошки. Затем Семён должен уронить доминошку с номером 1 вправо, она, падая, заденет доминошки с номерами 2 и 3, а доминошка 3, падая, заденет доминошку 4, таким образом все доминошки упадут. |
| 2 |
1 1
1
1
100000
1
1 100000 |
10000000000 |
Перед Семёном стоит одна доминошка стоимостью 10000000000 |