9662번 - 돌 게임 8

문제

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

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

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

입력

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

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

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

출력

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

제한

힌트