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