Buying cards

Interview

Time limit1sMemory limit256 MB

Summary

Given pack prices P_1 to P_N, choose packs whose card counts sum to exactly N to maximize the total price.

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

Problem

Collecting PS cards is a fad in Mingyu's neighborhood right now.

A PS card shows the handle and the face of someone well known in problem solving. Each card is painted a color that marks its grade, and there are 8 colors.

legend card
red card
orange card
purple card
blue card
teal card
green card
gray card

Cards are sold only in packs. There are $N$ kinds of pack: a pack holding 1 card, a pack holding 2 cards, and so on up to a pack holding $N$ cards. A pack holding $i$ cards costs $P_i$ won. The same kind of pack can be bought any number of times.

Mingyu believes a superstition: a pack with few cards still holds many high grade cards if it is expensive. So he wants to buy $N$ cards while paying as much money as possible.

For example, suppose there are 4 kinds of pack and $P_1 = 1$ , $P_2 = 5$ , $P_3 = 6$ , $P_4 = 7$ . The largest amount Mingyu can pay for 4 cards is 10 won. He buys the pack of 2 cards twice.

If $P_1 = 5$ , $P_2 = 2$ , $P_3 = 8$ , $P_4 = 10$ , buying the pack of 1 card four times costs 20 won, and that is the largest amount.

If $P_1 = 3$ , $P_2 = 5$ , $P_3 = 15$ , $P_4 = 16$ , buying the pack of 3 cards and the pack of 1 card costs 18 won, and that is the largest amount.

Given the pack prices, write a program that finds the largest amount Mingyu pays to buy $N$ cards. He cannot buy more than $N$ cards and throw the extras away to end up with $N$ . The card counts of the packs he buys must add up to exactly $N$ .

Input

The first line contains the number of cards $N$ that Mingyu wants to buy. ( $1 \le N \le 1000$ )

The second line contains $P_1$ through $P_N$ in order. ( $1 \le P_i \le 10000$ )

Output

Print the largest amount Mingyu pays to end up with $N$ cards.

Examples6

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