ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1841. Канатные дороги

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Недавно Вова купил новый широкоугольный объектив для своего фотоаппарата. Теперь он мечтает снять запоминающуюся панораму. Для этого он решил подняться на вершину ближайшей горы.
До вершины можно добраться по узкой извилистой тропинке, которая идёт вверх по склону. Вова мысленно ввёл систему координат, направив ось OY вдоль склона по направлению от подножия к вершине, а ось OX — перпендикулярно ей. Тропинка представляет собой ломаную из n звеньев, вершины которой следуют в порядке строгого возрастания y-координаты. Для каждого звена ломаной Вове известно время, которое понадобится, чтобы изменить x-координату на единицу при прохождении этого звена.
Кроме того, Вова может воспользоваться канатными дорогами. Эти дороги начинаются в некоторой точке тропинки, идут строго вверх по склону параллельно оси OY и заканчиваются в точке следующего пересечения с тропинкой. Для каждой канатной дороги известно время путешествия по ней.
Помогите Вове подняться на вершину горы, пока не стемнело! Учтите, что Вова столь целеустремлён, что откажется идти вниз по склону, даже если это поможет ему добраться до вершины быстрее.

Исходные данные

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

Результат

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

Примеры

исходные данныерезультат
4
0 5 15 10 0
1 1 1 100
1 1 7 1
1 0
1 0
15
3
0 10 0 10
10 0
10 1 10 1
10 0
101
Автор задачи: Денис Дублённых
Источник задачи: Ural SU Contest. Petrozavodsk Summer Session, August 2010