2255: NIKOLA
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：39
Solved：5
Description
有一行 n 个格子，编号为 1~n ，Nikola 从 1 号格子出发，想要前往 n 号格子。
他的行程包含若干次跳跃，第一次只能跳到 2 号格子，接下来的跳跃必须满足以下条件：
▲如果他向 n 号格子的方向跳跃，那么每次必须比前一次多跳一个距离的格子。
▲如果他向 1 号格子的方向跳跃，那么每次必须与上一次的跳跃距离完全相同。
例如，在第一次跳跃之后（位于2 号格），Nikola 可以选择跳到 4 或者1 。每进入一个格子，Nikola 都要支付相应的入场费。第 i 个格子需要付费 ai。他希望在能到达 n 号格的前提下尽可能少的花钱。你需要求出这个最小值。
他的行程包含若干次跳跃，第一次只能跳到 2 号格子，接下来的跳跃必须满足以下条件：
▲如果他向 n 号格子的方向跳跃，那么每次必须比前一次多跳一个距离的格子。
▲如果他向 1 号格子的方向跳跃，那么每次必须与上一次的跳跃距离完全相同。
例如，在第一次跳跃之后（位于2 号格），Nikola 可以选择跳到 4 或者1 。每进入一个格子，Nikola 都要支付相应的入场费。第 i 个格子需要付费 ai。他希望在能到达 n 号格的前提下尽可能少的花钱。你需要求出这个最小值。
Input
第1 行一个整数 n ，表示格子的数量。
接下来的 n 行，每行一个整数 ai ，依次表示 1~n 号格子的入场费。
接下来的 n 行，每行一个整数 ai ，依次表示 1~n 号格子的入场费。
Output
输出一行一个整数，表示最小的花费。
注意：刚开始所在的 1 号格子不计费，但多次经过同一个格子，每次都需要计费。
注意：刚开始所在的 1 号格子不计费，但多次经过同一个格子，每次都需要计费。
Sample Input Copy
6
1
2
3
4
5
6Sample Output Copy
12HINT
【输入样例 2】
8
2
3
4
3
1
6
1
4
【输出样例 2】
14
【样例 1 解释】Nikola 的路线为 1 -2 - 1- 3 - 6 。共花费 2+1+3+6=12 。
【数据规模】
对于 100%的数据：2 ≤ n ≤ 1000；1 ≤ ai ≤ 500。
8
2
3
4
3
1
6
1
4
【输出样例 2】
14
【样例 1 解释】Nikola 的路线为 1 -2 - 1- 3 - 6 。共花费 2+1+3+6=12 。
【数据规模】
对于 100%的数据：2 ≤ n ≤ 1000；1 ≤ ai ≤ 500。