시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB49946273269.758%

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 가져갈 수 있는 돌의 개수는 정해져있다. 돌을 올바른 개수만큼 가져갈 수 있는 방법이 없는 사람이 게임을 지게 된다.

M과 가져갈 수 있는 돌의 개수가 주어졌을 때, 창영이가 이기는 N중에서 1보다 크거나 같고, M보다 작거나 같은 것의 개수를 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력

첫째 줄에 M이 주어진다. (1 ≤ M ≤ 109)

둘째 줄에는 가져갈 수 있는 방법의 수 K가 주어진다. (1 ≤ K ≤ 22)

셋째 줄에는 가져갈 수 있는 돌의 개수가 공백으로 구분되어서 주어진다. 개수는 1보다 크거나 같고, 22보다 작거나 같으며, 중복되는 수는 없다. 또, 오름차순으로 주어진다.

출력

창영이가 이기는 N의 개수를 출력한다. (1 ≤ N ≤ M)

예제 입력 1

20
3
1 2 3

예제 출력 1

5

예제 입력 2

999
1
1

예제 출력 2

499

예제 입력 3

1000000000
2
1 2

예제 출력 3

333333333

예제 입력 4

6543
5
2 4 7 11 20

예제 출력 4

1637

출처