P2672 [NOIP 2015 普及组] 推销员

NOIP2015 普及组 T4

阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有 $N$ 家住户，第 $i$ 家住户到入口的距离为 $S_i$ 米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的 $X$ 家住户推销产品，然后再原路走出去。 阿明每走 $1$ 米就会积累 $1$ 点疲劳值，向第 $i$ 家住户推销产品会积累 $A_i$ 点疲劳值。阿明是工作狂，他想知道，对于不同的 $X$，在不走多余的路的前提下，他最多可以积累多少点疲劳值。

无

无

**输入输出样例 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$。