Лето в Берляндии длится \(n\) дней, цена одной порции мороженого в \(i\)-й день равна \(c_i\). За лето Таня хочет съесть ровно \(k\) порций мороженого. При этом в \(i\)-й день она решила, что съест не менее \(a_i\) порций, но не более \(b_i\) (\(a_i \le b_i\)). Иными словами, пусть \(d_i\) равно количеству порций, сколько она съест в \(i\)-й день. Тогда \(d_1+d_2+\dots+d_n=k\) и \(a_i \le d_i \le b_i\) для каждого \(i\).
Учитывая, что порции мороженого можно есть только в день покупки, найдите минимальную сумму денег, сколько Таня потратит на мороженое летом.
Выходные данные
Выведите минимальную сумму денег, которую Таня может потратить на мороженое летом. Если у Тани не существует способа так покупать и есть мороженое, чтобы удовлетворить все требования, то выведите -1.
Примечание
В первом примере Тане надо съесть \(3\) порции мороженого в первый день, \(1\) порцию мороженого во второй день и \(3\) порции мороженого в третий день. В таком случае, сумма потраченных денег равна \(3\cdot6+1\cdot4+3\cdot3=31\). Можно показать, что любой другой допустимый способ съесть ровно \(7\) порций мороженого потребует больших расходов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 7
3 5 6
0 3 4
3 3 3
|
31
|
|
2
|
1 45000
40000 50000 100000
|
4500000000
|
|
3
|
3 100
2 10 50
50 60 16
20 21 25
|
-1
|
|
4
|
4 12
2 5 1
1 2 2
2 3 7
3 10 4
|
35
|