g6-08101. 回收的钢条 未做

废品站收到一根长 $n$ 米的钢条，可以把它切成若干段出售，每段长度必须是正整数米，各段长度之和正好等于 $n$；也可以整根不切直接卖。长度为 $i$ 米的一段能卖 $p_i$ 元。切成的各段不分先后，收益只看切出了哪些长度。求最大总收入。

第一行一个整数 $n$。

第二行 $n$ 个整数 $p_1,p_2,\dots ,p_n$。

一行一个整数，表示最大总售价。

输入 1

5
1 5 8 9 10

输出 1

13

切成 2 米和 3 米两段，售价 $5+8=13$；整根卖只有 10 元。

$1\le n\le 2000$，$0\le p_i\le 10^4$。保证答案在 64 位整数范围内。