3676 - 切绳子2
Time Limit : 1 秒
Memory Limit : 128 MB
一段长为n的绳子，可以切成很多段，并且有好几种切法，比如当n=4时，可以切成1 1 1 1， 1 1 2，1 3，2 2。
而每种长度有不同的价格。现在给定n，和每种长度绳子的价格，要求输出能切出的最大价格。
<span></span>
Input
每个测试占两行，第一行一个整数1<=n<=100,
接下来一行有n个数，第i个数表示长度为i的绳子的价格。单节绳子最大价格不超过10000
Output
每个测试输出占一行
Examples
Input Format
2 1 3 3 2 3 4
Output Format
3 6