Автор: | Жюри летних сборов 2009 | Ограничение времени: | 2 сек | |
Входной файл: | bakery.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | bakery.out | |||
Максимальный балл: | 100 |
Пекарня города Малоярославца способна произвести до 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 |
|
|