Недавно Вова купил новый широкоугольный объектив для своего фотоаппарата. Теперь он мечтает снять запоминающуюся панораму. Для этого он решил подняться на вершину ближайшей горы.

До вершины можно добраться по узкой извилистой тропинке, которая идёт вверх по склону. Вова мысленно ввёл систему координат, направив ось OY вдоль склона по направлению от подножия к вершине, а ось OX — перпендикулярно ей. Тропинка представляет собой ломаную из n звеньев, вершины которой следуют в порядке строгого возрастания y-координаты. Для каждого звена ломаной Вове известно время, которое понадобится, чтобы изменить x-координату на единицу при прохождении этого звена.

Кроме того, Вова может воспользоваться канатными дорогами. Эти дороги начинаются в некоторой точке тропинки, идут строго вверх по склону параллельно оси OY и заканчиваются в точке следующего пересечения с тропинкой. Для каждой канатной дороги известно время путешествия по ней.

Помогите Вове подняться на вершину горы, пока не стемнело! Учтите, что Вова столь целеустремлён, что откажется идти вниз по склону, даже если это поможет ему добраться до вершины быстрее.

В первой строке записано целое число n (1 ≤ n ≤ 10⁵) — количество отрезков, из которых состоит тропинка. В следующей строке через пробел записано n + 1 целое число — x-координаты концов этих отрезков в порядке от подножия склона к вершине. x-координаты любых двух последовательных вершин ломаной различны. В i-й из следующих n строк записаны целые числа v_i и m_i — время, необходимое на изменение x-координаты на единицу при прохождении по i-му отрезку, и количество канатных дорог, начинающихся на i-м отрезке, соответственно. Далее в строке идёт m_i пар чисел, описывающих канатные дороги. Каждая дорога задаётся x-координатой её начала и временем, необходимым на её прохождение. Канатные дороги описаны в порядке от подножия к вершине. Никакие две канатные дороги не начинаются в одной точке. Если канатная дорога начинается в общей точке двух отрезков тропинки, то она присутствует в описании только одного отрезка. Гарантируется, что все канатные дороги заканчиваются на тропинке. Числа в строках разделены пробелами. Все координаты целые и не превосходят по модулю 10⁶. Все времена целые, положительные и не превосходят 10⁶. Общее количество канатных дорог не превосходит 10⁵.

Выведите минимальное время, за которое можно добраться до вершины.