题目背景

NOIP2015 普及组 T4

题目描述

阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有 $N$ 家住户，第 $i$ 家住户到入口的距离为 $S_i$ 米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的 $X$ 家住户推销产品，然后再原路走出去。

阿明每走 $1$ 米就会积累 $1$ 点疲劳值，向第 $i$ 家住户推销产品会积累 $A_i$ 点疲劳值。阿明是工作狂，他想知道，对于不同的 $X$，在不走多余的路的前提下，他最多可以积累多少点疲劳值。

输入格式

第一行有一个正整数 $N$，表示螺丝街住户的数量。

接下来的一行有 $N$ 个非负整数，其中第 $i$ 个整数 $S_i$ 表示第 $i$ 家住户到入口的距离。数据保证 $S_1 \le S_2 \le \cdots \le S_n <10^8$。

接下来的一行有 $N$ 个正整数，其中第 $i$ 个整数 $A_i$ 表示向第 $i$ 户住户推销产品会积累的疲劳值。数据保证 $A_i<1000$。

输出格式

输出 $N$ 行，每行一个正整数，第 $i$ 行整数表示当 $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

说明与提示

输入输出样例 1 说明

$X=1$：向住户 $5$ 推销，往返走路的疲劳值为 $5+5$，推销的疲劳值为 $5$，总疲劳值为 $15$。

$X=2$：向住户 $4,5$ 推销，往返走路的疲劳值为 $5+5$，推销的疲劳值为 $4+5$，总疲劳值为 $5+5+4+5=19$。

$X=3$：向住户 $3,4,5$ 推销，往返走路的疲劳值为 $5+5$，推销的疲劳值 $3+4+5$，总疲劳值为 $5+5+3+4+5=22$。

$X=4$：向住户 $2,3,4,5$ 推销，往返走路的疲劳值为 $5+5$，推销的疲劳值 $2+3+4+5$，总疲劳值 $5+5+2+3+4+5=24$。

$X=5$：向住户 $1,2,3,4,5$ 推销，往返走路的疲劳值为 $5+5$，推销的疲劳值 $1+2+3+4+5$，总疲劳值 $5+5+1+2+3+4+5=25$。

输入输出样例 2 说明

$X=1$：向住户 $4$ 推销，往返走路的疲劳值为 $4+4$，推销的疲劳值为 $4$，总疲劳值 $4+4+4=12$。

$X=2$：向住户 $1,4$ 推销，往返走路的疲劳值为 $4+4$，推销的疲劳值为 $5+4$，总疲劳值 $4+4+5+4=17$。

$X=3$：向住户 $1,2,4$ 推销，往返走路的疲劳值为 $4+4$，推销的疲劳值为 $5+4+4$，总疲劳值 $4+4+5+4+4=21$。

$X=4$：向住户 $1,2,3,4$ 推销，往返走路的疲劳值为 $4+4$，推销的疲劳值为 $5+4+3+4$，总疲劳值 $4+4+5+4+3+4=24$。或者向住户 $1,2,4,5$ 推销，往返走路的疲劳值为 $5+5$，推销的疲劳值为 $5+4+4+1$，总疲劳值 $5+5+5+4+4+1=24$。

$X=5$：向住户 $1,2,3,4,5$ 推销，往返走路的疲劳值为 $5+5$，推销的疲劳值为 $5+4+3+4+1$，总疲劳值 $5+5+5+4+3+4+1=27$。

数据范围

对于 $20\%$ 的数据，$1 \le N \le20$；
对于 $40\%$ 的数据，$1\le N \le 100$；
对于 $60\%$ 的数据，$1 \le N \le 1000$；
对于 $100\%$ 的数据，$1 \le N \le 10^5$。

18
1 273 649 1583 2026 2156 2811 3247 3272 3635 3815 4247 4582 5253 5277 5624 6247 6914
433 822 327 143 998 991 71 171 614 905 102 551 688 406 243 440 113 623

14451
15449
16440
17345
18167
18855
19469
20020
20460
20893
21299
21626
21869
22040
22183
22296
22398
22469