Watering the Plants

문제

Bessie's garden has $NN$ plants labeled $11$ through $NN$ ($2\le N\le 5\cdot {10}^{5}2\backslash leq\; N\backslash leq\; 5\backslash cdot\; 10^5$) from left to right. Bessie knows that plant $ii$ requires at least $w_{i}w\_i$ ($0\le w_i\le {10}^{6}0\backslash leq\; w\_i\; \backslash leq\; 10^6$) units of water.

Bessie has a very peculiar irrigation system with $N-1N-1$ canals, numbered $11$ through $N-1N-1$. Each canal $ii$ has an associated unit cost $c_{i}c\_i$ ($1\le c_i\le {10}^{6}1\backslash le\; c\_i\backslash le\; 10^6$), such that Bessie can pay $c_{i}kc\_i\; k$ to provide plants $ii$ and $i+1i+1$ each with $kk$ units of water, where $kk$ is a non-negative integer.

Bessie is busy and may not have time to use all the canals. For each $2\le i\le N2\backslash leq\; i\; \backslash leq\; N$ compute the minimum cost required to water plants $11$ through $ii$ using only the first $i-1i-1$ canals.

입력

The first line contains a single positive integer $NN$.

The second line contains $NN$ space-separated integers $w_1,\dots ,w_{N}w\_1,\; \backslash ldots,\; w\_N$.

The third line contains $N-1N-1$ space-separated integers $c_1,\dots ,c_{N-1}c\_1,\; \backslash ldots,\; c\_\{N-1\}$.

출력

Output $N-1N-1$ newline-separated integers. The $(i-1)(i-1)$th integer should contain the minimum cost to water the first $ii$ plants using the first $i-1i-1$ canals.

3
39 69 33
30 29

2070
2127

3
33 82 36
19 1

1558
676

8
35 89 44 1 35 3 62 50
7 86 94 62 63 9 49

623
4099
4114
6269
6272
6827
8827