题目描述

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

输入格式

第一行包含一个数$n$，如题目描述。

第二行包含$n$个数，表示在第$i$个点钻井判断是否有油需要的时间。

$n<=2000,t_i<=10^6$

输出格式

一个数字表示答案。

样例输入1

4
8 24 12 6

样例输出1

42

因为有100个点，所以改成了subtask的形式，只要挂了一个点就结束了。