Resort

Interview

Time limit2sMemory limit512 MB

Summary

Choose one-day, 3-day, and 5-day passes over a vacation with blocked days so every open day is covered at minimum cost, where 3 coupons buy a free one-day pass.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy, Prefix sum
Solved: No attempts yet

Problem

Suyeong wants to spend her summer vacation at the KOI resort, which has many attractions. A one-day pass costs 10,000 won. The resort is so large that one day is nowhere near enough to enjoy every attraction, so many visitors stay three days or more in a row. The KOI resort sells a 3-day pass for 25,000 won and a 5-day pass for 37,000 won. A 3-day pass comes with 1 coupon and a 5-day pass comes with 2 coupons. Three coupons can be exchanged for one one-day pass.

Pass	Price	Coupons
One-day pass	10,000 won	none
3-day pass	25,000 won	1 coupon
5-day pass	37,000 won	2 coupons

A 3-day pass and a 5-day pass are valid only on the 3 or 5 consecutive days that start on the day of purchase, but there is no need to use every day of that period.

Suyeong's summer vacation lasts $N$ days, and on $M$ of those days she cannot go to the resort because of other plans. She wants to spend every remaining day at the KOI resort, and she wants to pay as little as possible.

For example, suppose the vacation lasts 13 days and she cannot go on days 4, 6, 7, 11 and 12. The first row of the figure below is the 13-day vacation, with the days she cannot go painted black. The second and third rows are two ways of buying passes.

The second row works like this. On day 1 she buys a 3-day pass, uses it through day 3, and gets 1 coupon. On day 5 she buys a one-day pass. On day 8 she buys another 3-day pass, uses it through day 10, and gets 1 more coupon. On day 13 she buys a one-day pass. She pays 70,000 won in total.

The third row is cheaper. On day 1 she buys a 5-day pass, uses it through day 5 (skipping day 4), and gets 2 coupons. On day 8 she buys a 3-day pass, uses it through day 10, and gets 1 more coupon. On day 13 she exchanges the 3 coupons she collected for one one-day pass. She pays 62,000 won in total.

Given the length of the vacation and the days she cannot go, write a program that computes the minimum amount Suyeong has to pay to use the resort.

Input

The first line contains the number of vacation days $N$ ( $1 \le N \le 100$ ) and the number of days Suyeong cannot go to the resort $M$ ( $0 \le M \le N$ ), in that order, separated by a space.

If $M$ is greater than 0, the second line contains the $M$ days she cannot go, as integers between 1 and $N$ in increasing order. If $M$ is 0, the second line is not given.

Output

Print on one line the minimum amount she has to pay to enter the resort on every day except the days she cannot go.

Examples5

Example 1
Input
```
13 5
4 6 7 11 12
```
Expected output
```
62000
```

Example 2

Input

50 10
3 5 7 11 15 16 22 23 24 34

Expected output

Example 3
Input
```
1 0
```
Expected output
```
10000
```
Example 4
Input
```
1 1
1
```
Expected output
```
0
```
Example 5
Input
```
5 0
```
Expected output
```
37000
```