Buying Cards 2

Interview

Time limit1sMemory limit256 MB

Summary

Given prices for card packs of sizes 1 to N, find the cheapest way to buy packs whose card counts sum to exactly N.

Level: Easy3 of 10
Topics: Dynamic programming
Solved: No attempts yet

Statement

These days, collecting PS cards is popular in Mingyu's neighborhood.

A PS card has the ID and face of a famous person in Problem Solving printed on it. Each card is painted with a color that indicates its grade, and there are 8 grades:

Legend card
Red card
Orange card
Purple card
Blue card
Teal card
Green card
Gray card

Cards can only be bought in card packs, and there are N kinds of card packs: a pack containing 1 card, a pack containing 2 cards, ..., and a pack containing N cards.

Mingyu spent too much money last week. So today he wants to buy N cards while paying as little as possible. The price of a card pack containing i cards is Pi won.

For example, if there are 4 kinds of card packs and P1 = 1, P2 = 5, P3 = 6, P4 = 7, the minimum amount Mingyu has to pay to get 4 cards is 4 won. He can buy the pack containing 1 card four times.

If P1 = 5, P2 = 2, P3 = 8, P4 = 10, buying the pack containing 2 cards twice costs 4 won, and this is the minimum amount Mingyu has to pay.

Given the prices of the card packs, write a program that finds the minimum amount Mingyu has to pay to buy N cards. It is not possible to buy more than N cards and throw away the leftovers to end up with N. That is, the sum of the numbers of cards in the purchased packs must equal N.

Input

The first line gives N, the number of cards Mingyu wants to buy. (1 ≤ N ≤ 1,000)

The second line gives Pi from P1 to PN in order. (1 ≤ Pi ≤ 10,000)

Output

Print the minimum amount Mingyu has to pay to get N cards.

Hint

Examples5

Example 1
Input
```
4
1 5 6 7
```
Expected output
```
4
```
Example 2
Input
```
5
10 9 8 7 6
```
Expected output
```
6
```
Example 3
Input
```
10
1 1 2 3 5 8 13 21 34 55
```
Expected output
```
5
```
Example 4
Input
```
10
5 10 11 12 13 30 35 40 45 47
```
Expected output
```
26
```
Example 5
Input
```
4
5 2 8 10
```
Expected output
```
4
```