Сад Беси имеет \(N\) растений, помеченных от \(1\) до \(N\)
(\(2\leq N\leq 5\cdot 10^5\)) слева направо. Беси знает, что растение
\(i\) требует не менее \(w_i\) (\(0\leq w_i \leq 10^6\)) единиц воды.
У Беси своеобразная ирригационная система с \(N-1\) каналами,
пронумерованными от \(1\) до \(N-1\). Каждый канал \(i\) имеет ассоциированную с ним
стоимость \(c_i\) (\(1\le c_i\le 10^6\)), такую что Беси может заплатить
\(c_i*k\) чтобы обеспечить растение \(i\) и \(i+1\) каждое \(k\) единицами воды
где \(k\) неотрицательное целое число.
Беси сильно занята и может не иметь времени использовать все каналы.
Для каждого \(2\leq i \leq N\) вычислите минимальную стоимость требуемую,
чтобы доставить воду растениям от \(1\) до \(i\) используя только первые \(i-1\) каналов.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит положительное целое число
\(N\).
Вторая строка содержит \(N\) разделённых одиночными пробелами целых чисел
\(w_1, \ldots, w_N\).
Тртья строка содержит \(N-1\) разделённых одиночными пробелами целых чисел
\(c_1, \ldots, c_{N-1}\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(N-1\) целых чисел, каждое в отдельной строке. \((i-1)\)-ое целое число должно
представлять минимальную стоимость доставить воду к первым \(i\) растениям, используя
первые \(i-1\) каналов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
39 69 33
30 29
|
2070
2127
|