Stone Game 8

Time limit1sMemory limit128 MB

Summary

Count pile sizes up to M where the second player wins a take-away game with a fixed move set.

Level: Medium6 of 10
Topics: Game theory, Dynamic programming, Math
Solved: No attempts yet

Problem

The stone game is a game where two people take stones in alternating turns.

There are $N$ stones on a table. Sanggeun and Changyoung take stones one after the other, and the numbers of stones a player may take in one turn are fixed in advance. A player who cannot take one of the allowed numbers of stones on their turn loses the game. Sanggeun goes first, and both players play as well as they possibly can.

Given $M$ and the numbers of stones a player may take in one turn, write a program that counts how many values of $N$ between $1$ and $M$ let Changyoung win.

Input

The first line contains $M$ . ( $1 \le M \le 10^9$ )

The second line contains the number of allowed moves $K$ . ( $1 \le K \le 22$ )

The third line contains the $K$ numbers of stones a player may take in one turn, separated by spaces. Each number is at least $1$ and at most $22$ , no number repeats, and they are given in increasing order.

Output

Print how many values of $N$ let Changyoung win. ( $1 \le N \le M$ )

Examples4

Example 1
Input
```
20
3
1 2 3
```
Expected output
```
5
```
Example 2
Input
```
999
1
1
```
Expected output
```
499
```
Example 3
Input
```
1000000000
2
1 2
```
Expected output
```
333333333
```
Example 4
Input
```
6543
5
2 4 7 11 20
```
Expected output
```
1637
```