Description

A Ming is a salesman. He is assigned to promote his company’s products on Screw Street. Screw Street is a dead-end; the exit and entrance are the same. One side of the street is a wall, and the other side has households. There are $N$ households on Screw Street, and the $i$-th household is $S_i$ meters from the entrance. Because multiple households can live in the same building, several households may be at the same distance from the entrance. A Ming will enter from the entrance, promote products to $X$ households on Screw Street one by one, and then walk back along the same route.

For every $1$ meter he walks, he accumulates $1$ fatigue point. Promoting to the $i$-th household accumulates $A_i$ fatigue points. A Ming is a workaholic. He wants to know, for different values of $X$, under the premise of not walking any extra distance, what is the maximum total fatigue he can accumulate.

Input Format

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

The next line contains $N$ non-negative integers; the $i$-th integer $S_i$ is the distance from the $i$-th household to the entrance. It is guaranteed that $S_1 \le S_2 \le \cdots \le S_n <10^8$.

The next line contains $N$ positive integers; the $i$-th integer $A_i$ is the fatigue accumulated by promoting to the $i$-th household. It is guaranteed that $A_i<1000$.

Output Format

Output $N$ lines, each with one positive integer. The integer on the $i$-th line denotes the maximum total fatigue when $X=i$.

5
1 2 3 4 5
1 2 3 4 5

15
19
22
24
25

5
1 2 2 4 5
5 4 3 4 1

12
17
21
24
27

Hint

Explanation for Sample 1:

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

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

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

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

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

Explanation for Sample 2:

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

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

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

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

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

Constraints:

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

Translated by ChatGPT 5