挖油
时间限制：10s 空间限制：128MB
题目描述
给出一条线段，在左端点点0与右端点n+1间有n个点(n<=2000)，并且在0到x之间的所有点都是有油的，在每个点钻井判断是否有油需要时间ti，求能够知道x的最坏情况下最少需要多少时间。
输入格式
第一行包含一个数n，如题目描述。
第二行包含n个数，表示在第i个点钻井判断是否有油需要的时间。
输出格式
输出包含一行，最坏情况下最少需要多少时间。
样例输入
4 8 24 12 6
样例输出
42
提示
对于100%的数据，n<=2000,ti<=10^6
题目来源
2011福建集训