28259번 - 초콜릿 트리 만들기

코코는 초콜릿을 가지고 트리 만들기 게임을 하려고 한다. 각각의 초콜릿에는 $0$ 이상 $N-1$ 이하의 정수가 쓰여 있다. 트리 만들기 게임은 각 노드에 초콜릿이 하나씩 놓여 있는 이진 트리를 만드는 게임으로, 다음과 같이 진행된다.

• 맨 처음에는 트리의 루트를 만들고, 아무 정수가 쓰여진 초콜릿을 하나 놓는다.
• 그 이후에는 다음을 반복한다.
  • 리프 노드를 하나 선택한다. 그 자리의 초콜릿에 쓰인 수를 $M$이라고 하자.
  • 선택한 노드 아래에 자식 노드 2개를 추가하고, 합이 $M$ 또는 $N+M$인 두 수를 골라서 그 두 수가 쓰인 초콜릿을 두 자식 노드 자리에 놓는다.

코코는 수 $a_1,a_2,\cdots ,a_k$가 쓰여 있는 초콜릿은 무한히 많이 갖고 있지만, 다른 수가 쓰여 있는 초콜릿은 갖고 있지 않아 한별이에게 빌려야 한다. 모든 리프의 깊이가 $H$인 트리를 만든다고 할 때, 한별이에게 최소 몇 개의 초콜릿을 빌려야 트리를 완성할 수 있는지 구해 보자. 어떤 노드의 깊이는 그 노드에서 루트까지의 최단경로 상에 있는 간선의 개수로 정의한다.

첫 줄에는 $N$, $H$, $k$의 값이 주어진다. ($2\le N\le 500$, $1\le H\le 60$, $1\le k\le N$)

다음 줄에는 $a_1,a_2,\cdots ,a_k$의 값이 주어진다. ($0\le a_i<N$) $a_i$의 값은 서로 다르다.

한별이에게 빌려야 하는 초콜릿의 개수의 최솟값을 한 줄에 출력한다.