Fruits

문제

Supermarkets usually have fruits for sale in sections, where each section is dedicated to a single type of fruit. The supermarket that Benson the Rabbit is visiting has $NN$ sections and $NN$ types of fruits. The sections are numbered from $11$ to $NN$ and each fruit is numbered from $11$ to $NN$.

The $ii$th fruit has tastiness $ii$ and cost $C_{i}C\_i$. It is guaranteed that C_i &le; C_j for all 1 &le; i < j &le; N.

Each of the $NN$ sections is to be assigned a distinct type of fruit. At the moment, the type of fruit assigned to section $jj$ is $A_{j}A\_j$. If $A_j=-1A\_j\; =\; -1$, then section $jj$ is empty. Otherwise, fruit $A_{j}A\_j$ is already assigned to section $jj$. Once all $NN$ fruits have been assigned, the supermarket will open and Benson will enter the supermarket to buy the fruits.

Benson is very picky but also in a rush, so he will visit the sections in increasing order. Benson’s basket is initially empty, and when he reaches a section, he will compare the tastiness of the fruit in that section to the tastiness of all of the fruits in his basket. If his basket is empty, or if the tastiness of the fruit at the current section is greater than the tastiness of every other fruit in his basket, Benson will add that fruit to his basket.

To maximise revenue, you have been tasked with assigning the fruits to the sections such that the sum of cost of fruits that Benson adds to his basket is maximised. As Benson is rushing for time, he might only visit the first few sections before going straight to the cashier. Help compute, for each $kk$ from $11$ to $NN$, the maximum possible revenue that can be achieved if Benson only visits the first $kk$ sections given that the arrangement of fruits can change for different $kk$.

입력

Your program must read from standard input.

The input starts with a line with one positive integer $NN$.

The second line contains $NN$ integers where the ith integer represents $A_{i}A\_i$.

The third line contains $NN$ integers where the ith integer represents $C_{i}C\_i$.

출력

Your program must print to standard output.

The output should contain a $NN$ integers on a single line. The kth one should be the maximum sum of costs that Benson will pay if the fruits are assigned optimally if he visits only the first $kk$ sections.

5
-1 -1 -1 -1 -1
1 1 1 1 1

1 2 3 4 5

5
-1 3 -1 -1 -1
1 2 2 2 3

3 4 7 9 9

13
-1 -1 5 6 -1 -1 7 11 -1 -1 10 -1 -1
1 1 1 1 1 1 1 1 1 1 1 1 1

1 2 3 4 5 6 6 7 8 9 9 9 9

10
-1 -1 -1 -1 5 -1 -1 -1 9 -1
5 11 24 27 35 60 72 81 91 92

92 173 245 305 305 332 356 367 406 498