35031번 - But when she jumps it gets faster

문제

정휘는 신년을 맞아 좋아하는 캐릭터가 나오는 영상을 보면서 휴식을 취하고 있다.

정휘가 보고 있는 영상은 $L$ 프레임 길이로, 한 프레임당 하나의 장면이 재생된다. 따라서 영상은 $L$개의 장면으로 이루어져 있고, 이 장면들을 프레임 당 하나씩 연속해서 틀면 동영상이 재생된다. 이 중 $K$개의 장면에서는 영상의 캐릭터가 점프를 한다. 구체적으로, $p_1, p_2, \dots p_K$번째 장면에서 캐릭터가 점프한다.

정휘는 영상이 너무 좋은 나머지, 영상의 무한 반복 버전을 찾아냈다. 거기에 더해, 이 버전은 영상의 캐릭터가 점프할 때마다 속도가 빨라진다!

영상은 프레임 단위로 재생된다. 처음에는 1프레임에 1개의 장면이 재생된다. 그 이후 캐릭터가 점프하는 장면을 재생할 때마다, 속도는 2배, 3배, 4배... 로 빨라진다.

예를 들어, 지금 영상이 5배속으로 재생되고 있다고 하자. 이 경우 영상은 1프레임에 5개의 장면을 재생하게 된다. 만약 이 5개 장면 중 2개에서 캐릭터가 점프를 한다면, 다음 프레임에는 7배속이 되어 1프레임에 7개의 장면을 재생하게 된다. 만약 배속이 충분히 빠르다면, 1프레임에 전체 영상을 여러 번 재생할 수 있음에 유의하라.

영상의 어떤 지점에서 캐릭터가 점프하는지가 주어질 때, 영상을 총 $N$번 반복해서 재생하려면 몇 프레임이 걸리는지 출력하여라.

입력

첫 번째 줄에 $N,ドル $L,ドル $K$가 공백을 사이에 두고 주어진다.

두 번째 줄에 $p_1,ドル $p_2,ドル $\dots,ドル $p_K$가 공백을 사이에 두고 차례로 주어진다.

출력

영상을 $N$번 재생하기 위해 필요한 최소 프레임 수를 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• 1ドル\le N\le 10^{12}$
• 1ドル\le K\le L\le 10^6$
• 1ドル\le p_1<p_2<\cdots <p_K\le L$

노트