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

Условие

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

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

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

В первой строке содержится натуральное число n. Далее в n строках содержатся числа c_i, f_i, d_i. Затем в n − 1 строках содержатся числа g_i, e_i.

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

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

Ограничения

1 ≤ n ≤ 10⁵;

0 ≤ c_i, f_i, d_i, g_i, e_i ≤ 10⁹;

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

3
10 1 1
2 2 2
10 10 8
7 2
6 5

73