[NOIP 2015 普及组] 推销员

题目背景

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\) 时，阿明最多积累的疲劳值。

样例 #1

样例输入 #1

5
1 2 3 4 5
1 2 3 4 5

样例输出 #1

15
19
22
24
25

样例 #2

样例输入 #2

5
1 2 2 4 5
5 4 3 4 1

样例输出 #2

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 100000\)。