B. Buying Croissants
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Womais aime manger des croissants. He will eat one croissant every day for the next 80 years.

The first attempt was to stockpile 29220 croissants, which is enough to last 80 years. Unfortunately, after a week (7 days), the unconsumed croissants all went bad and became inedible. It seems that every croissant has this same shelf-life of 7 days. For example, if a croissant is bought on Monday, then it will be good through Sunday and become inedible on the next Monday.

For attempt two, Womais used his clairvoyance to see the croissant prices for the next $$$n$$$ days. Now he needs to determine the least cost of buying croissants to satisfy his croissant needs for the next $$$n$$$ days. It is safe to assume that the baker will never run out of croissants.

Input

The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 29220$$$), giving the number of days in question.

The second line of input contains $$$n$$$ space-separated integers $$$c_i$$$ ($$$1 \le c_i \le 4\cdot10^4$$$), where $$$c_i$$$ is the cost of one croissant on day $$$i$$$.

Output

The only line of output should contain a single integer, which is the least cost for Womais to eat one croissant per day for the next $$$n$$$ days.

Examples
Input
7
1 9 9 9 9 9 9
Output
7
Input
8
1 9 9 9 9 9 9 9
Output
16
Input
9
9 2 102 820 199 40000 1 37 42
Output
22