题目描述

给定一根长度为n的钢条，以及一个价格表a[1..n]，其中a[i]表示长度为i的钢条的售价。要求将钢条切割成若干段（可以不切割），使得总售价最大。

输入描述

第一行一个整数n，表示钢条的长度。 第二行n个整数a[1], a[2], ..., a[n]，分别表示长度为1到n的钢条的售价。

输出描述

输出一个整数，表示切割钢条能获得的最大总售价。

输入样例

4
1 5 8 9

输出样例

10

数据范围

• 1 ≤ n ≤ 100
• 1 ≤ a[i] ≤ 1000