挖油

时间限制:10s      空间限制:128MB

题目描述

给出一条线段,在左端点点0与右端点n+1间有n个点(n<=2000),并且在0x之间的所有点都是有油的,在每个点钻井判断是否有油需要时间ti,求能够知道x的最坏情况下最少需要多少时间。
 


输入格式

第一行包含一个数n,如题目描述。
第二行包含n个数,表示在第i个点钻井判断是否有油需要的时间。
 


输出格式

输出包含一行,最坏情况下最少需要多少时间。
 


样例输入

4
8 24 12 6
 

样例输出

42
 

提示

对于100%的数据,n<=2000,ti<=10^6


题目来源

2011福建集训