Minimum Cost for Wire Length Determination

After returning to her hometown, her new job is to repair wires. One day, she finds that a wire is broken. It is known that the required wire length is one of the integers in \(\{1,2,\cdots,n\}\). To determine the exact required length, she can purchase a wire of length \(i\) for a cost of \(a_i\) (with \(a_1 \le a_2 \le \cdots \le a_n \le 10^9\)). After purchasing a wire of length \(i\), she will know whether the required wire length is greater than \(i\) or not.

Your task is to determine the minimum amount of money she needs to spend so that, regardless of the actual required length, she can determine it exactly.

A possible dynamic programming formulation is as follows. Let \(dp(k)\) be the minimum cost required to determine the wire length when there are \(k\) possible values. Clearly, \(dp(0)=dp(1)=0\) (if there is at most one possibility, no query is needed). For \(k \ge 2\), the recurrence is given by:

[ dp(k) = \min_{1 \le i < k} \Big( a_i + \max(dp(i),, dp(k-i)) \Big), ]

Here, choosing \(i\) corresponds to buying a wire of length \(i\) for the cost \(a_i\). If the answer is that the required length is greater than \(i\), the remaining possibilities are \(\{i+1, i+2, \ldots, k\}\) (which is a set of size \(k-i\)); otherwise, the answer implies that the required length is within \(\{1,2, \ldots, i\}\) (which is a set of size \(i\)).

Determine \(dp(n)\), where \(n\) is the total number of possible wire lengths.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) (\(1 \le n \le \text{some limit}\)), representing the number of possible wire lengths.
• The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\), which are the costs corresponding to each wire length and satisfy \(a_1 \le a_2 \le \cdots \le a_n\).

outputFormat

Output a single integer: the minimum amount of money she must spend to guarantee that she can determine the required wire length.

sample

2
3 5

3