Bessie's garden has N plants labeled 1 through N(2≤N≤5⋅105) from left to right. Bessie knows that plant i requires at least wi (0≤wi≤106) units of water.
Bessie has a very peculiar irrigation system with N−1 canals, numbered 1 through N−1. Each canal i has an associated unit cost ci (1≤ci≤106), such that Bessie can pay cik to provide plants i and i+1 each with k units of water, where k is a non-negative integer.
Bessie is busy and may not have time to use all the canals. For each 2≤i≤N compute the minimum cost required to water plants 1 through i using only the first i−1 canals.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains a single positive integer N.
The second line contains N space-separated integers w1,…,wN.
The third line contains N−1 space-separated integers c1,…,cN−1.
OUTPUT FORMAT (print output to the terminal / stdout):
Output N−1 newline-separated integers. The (i−1)th integer should contain the minimum cost to water the first i plants using the first i−1 canals.
SAMPLE INPUT:
3
39 69 33
30 29
SAMPLE OUTPUT:
2070
2127
The minimum cost to water the first 2 plants using the first canal is to pay 30⋅69=2070 by using the first canal 69 times.
The minimum cost to water the first 3 plants is to use the first canal 39 times and the second canal 33 times, paying 39⋅30+29⋅33=2127.
SAMPLE INPUT:
3
33 82 36
19 1
SAMPLE OUTPUT:
1558
676
SAMPLE INPUT:
8
35 89 44 1 35 3 62 50
7 86 94 62 63 9 49
SAMPLE OUTPUT:
623
4099
4114
6269
6272
6827
8827
SCORING:
Input 4: N≤200, and all wi ≤200.
Inputs 5-6: All wi ≤200.
Inputs 7-10: N≤5000.
Inputs 11-14: All wi and ci are generated independently and uniformly at random.
Inputs 15-19: No additional constraints.
Problem credits: Benjamin Qi
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
