Задача D. Пекарня

Автор:Жюри летних сборов 2009   Ограничение времени:2 сек
Входной файл:bakery.in   Ограничение памяти:256 Мб
Выходной файл:bakery.out  

Условие

Пекарня города Малоярославца способна произвести до ci буханок хлеба в i-ый день. При этом каждая буханка хлеба обойдется пекарне в fi условных Малоярославских долларов. Известно, что для обеспечения города продовольствием в день требуется di буханок хлеба, которые успешно будут употреблены населением. Оставшиеся буханки отправляются на склад и могут быть использованы в следующие дни. На складе можно в ночь с i ого на i+1 день хранить не более gi буханок, при этом хранение каждой буханки хлеба на складе обойдется пекарне в ei Малоярославских долларов.

Ваша задача — определить наименьшее количество денег, которое пекарня потратит на производство и хранение, чтобы обеспечить Малоярославец хлебом в течение n дней.

Формат входного файла

В первой строке содержится натуральное число n. Далее в n строках содержатся числа ci, fi, di. Затем в n − 1 строках содержатся числа gi, ei.

Формат выходного файла

Выведите единственное число — минимальное количество денег, необходимое пекарне. Если удовлетворить требованиям города невозможно, выведите -1.

Ограничения

1 ≤ n ≤ 105;

0 ≤ ci, fi, di, gi, ei ≤ 109;

Примеры тестов

Входной файл (bakery.in) Выходной файл (bakery.out)
1
3
10 1 1
2 2 2
10 10 8
7 2
6 5
73

0.040s 0.011s 15