Problem Background

NOIP2015 Junior Group T4

Problem Description

Aming is a salesman tasked with promoting his company's products on Screw Street. Screw Street is a dead-end road with the entrance and exit being the same point. On one side of the street is a wall, and on the other side are residences. There are $N$ households on Screw Street, with the distance from the entrance to the $i$-th household being $S_i$ meters. Since multiple households can reside in the same building, it is possible for multiple households to have the same distance from the entrance. Aming will enter from the entrance, sequentially promote products to $X$ households on Screw Street, and then return the same way.

Aming accumulates 1 point of fatigue for every meter walked, and promoting products to the $i$-th household accumulates $A_i$ points of fatigue. Aming is a workaholic and wants to know, for different values of $X$, the maximum fatigue he can accumulate without walking unnecessary distances.

Input Format

The first line contains a positive integer $N$, representing the number of households on Screw Street.

The next line contains $N$ positive integers, where the $i$-th integer $S_i$ represents the distance from the entrance to the $i$-th household. The data guarantees $S_1 \le S_2 \le \cdots \le S_n < 10^8$.

The following line contains $N$ positive integers, where the $i$-th integer $A_i$ represents the fatigue accumulated by promoting products to the $i$-th household. The data guarantees $A_i < 1000$.

Output Format

Output $N$ lines, each containing a positive integer. The $i$-th line integer represents the maximum fatigue Aming can accumulate when $X = i$.

Sample Input and Output

Sample Input #1

5
1 2 3 4 5
1 2 3 4 5

Sample Output #1

15
19
22
24
25

Sample Input #2

5
1 2 2 4 5
5 4 3 4 1

Sample Output #2

12
17
21
24
27

Notes

Sample 1 Explanation

$X=1$: Promote to household 5, round-trip walking fatigue is $5+5$, promotion fatigue is $5$, total fatigue is $15$.

$X=2$: Promote to households 4,5, round-trip walking fatigue is $5+5$, promotion fatigue is $4+5$, total fatigue is $19$.

$X=3$: Promote to households 3,4,5, round-trip walking fatigue is $5+5$, promotion fatigue is $3+4+5$, total fatigue is $22$.

$X=4$: Promote to households 2,3,4,5, round-trip walking fatigue is $5+5$, promotion fatigue is $2+3+4+5$, total fatigue is $24$.

$X=5$: Promote to households 1,2,3,4,5, round-trip walking fatigue is $5+5$, promotion fatigue is $1+2+3+4+5$, total fatigue is $25$.

Sample 2 Explanation

$X=1$: Promote to household 4, round-trip walking fatigue is $4+4$, promotion fatigue is $4$, total fatigue is $12$.

$X=2$: Promote to households 1,4, round-trip walking fatigue is $4+4$, promotion fatigue is $5+4$, total fatigue is $17$.

$X=3$: Promote to households 1,2,4, round-trip walking fatigue is $4+4$, promotion fatigue is $5+4+4$, total fatigue is $21$.

$X=4$: Promote to households 1,2,3,4, round-trip walking fatigue is $4+4$, promotion fatigue is $5+4+3+4$, total fatigue is $24$. Alternatively, promote to households 1,2,4,5, round-trip walking fatigue is $5+5$, promotion fatigue is $5+4+4+1$, total fatigue is $24$.

$X=5$: Promote to households 1,2,3,4,5, round-trip walking fatigue is $5+5$, promotion fatigue is $5+4+3+4+1$, total fatigue is $27$.

Data Range

For $20\%$ of the data, $1 \le N \le 20$;
For $40\%$ of the data, $1 \le N \le 100$;
For $60\%$ of the data, $1 \le N \le 1000$;
For $100\%$ of the data, $1 \le N \le 100000$.

见题面 Input 部分

见题面 Output 部分