문제
롤러코스터를 타기 위해 사람들이 줄을 서 있다. 누군가는 홀로 타기위해 줄을 서 있고, 어떤 사람들은 무리를 지어서 타고자 하는데, 만약에 한 번에 롤러 코스터를 타지 못할 경우에는 무리가 모두 탈 수 있을 때 까지 기다렸다 타고자 한다.
그리고 사람들은 롤러코스터를 매우 좋아하기 때문에 여러번 타려고 한다. 한 번 탈 때마다 1인당 1유로씩의 돈을 내게 된다. 롤러코스터는 최대 K명의 사람들을 한 번에 태울 수 있다. 롤러코스터를 타기 위해 서 있는 줄에서는 사람들이 모두 무리를 지어 서 있다. 여기서 무리란 한명 이상의 동시에 롤러코스터를 타고자 하는 사람들의 모임을 뜻한다. 롤러코스터는 총 R번 운행된다.
무리가 서 있는 순서대로 롤러코스터에 계속 타게 되는데, 만약 무리에 속한 모든 사람이 타지 못할 경우 다음 번에 롤러코스터를 타게 된다. 롤러 코스터가 끝나면 롤러 코스터를 탄 무리들은 다시 차례대로 현재의 줄의 맨 뒤 부터 원래의 순서를 유지하면서 줄을 선다.
롤러 코스터에 태울 수 있는 사람의 수와 운행 수, 그리고 무리를 이루는 사람들의 수가 주어졌을 때 얼마나 벌 수 있는지를 알아내는 프로그램을 작성하라.
이해를 돕기 위해 예시를보도록 하자.
R = 4 이고, K = 6 이며, 다음과 같이 처음에 4개의 무리가 줄을 서 있다. 숫자는 무리에 속한 사람의 수를 뜻한다. 1, 4, 2, 1
처음 운행을 하려고 할 때는 맨처음 무리와 두번째 무리가 타게 된다. 세번째 무리까지 타게 하려고 할 경우 롤러 코스터에 탑승하려는 사람의 수가 K보다 커지기 때문에 타질 못한다. 따라서 롤러코스터에 사람들을 태우고 남은 줄의 상태는 다음과 같다. 2, 1
그리고 롤러 코스터를 타고 나서 내린 사람들이 다시 줄을 섰을 경우는 다음과 같다. 2, 1, 1, 4
두번째 운행 시에는 2, 1, 1 이 롤러 코스터를 타게 되고, 남은 줄의 상태는 다음과 같으며, 4
롤러 코스터를 타고 내린 사람들이 다시 줄을 서면 줄의 상태는 다음과 같아진다. 4, 2, 1, 1
세번째에는 4, 2 로 이뤄진 무리가 롤러 코스터를 타게 되고, 1, 1이 남게 되며, 롤러 코스터가 운행을 마치고 나서 줄의 상태는 1, 1, 4, 2 가 된다. 마지막으로 1, 1, 4 가 롤러 코스터를 타게 되고, 총 21명의 사람을 태웠기 때문에 21유로를 얻게 된다.
입력
입력파일은 INPUT.TXT로 한다.
입력의 첫번째 줄에는 R과 K, 그리고 N이 입력된다(1≤R≤100,000,000, 1≤k≤1,000,000,000, 1≤N≤1,000). 그 다음 줄에는 줄을 이루고 있는 N개의 무리를 이루는 사람의 숫자가 입력되며, 먼저 입력되는 숫자가 처음에 앞에 서있는 무리를 의미한다. 무리를 이루는 사람의 수는 1이상 10,000,000 이하의 정수다.
출력
출력파일은 OUTPUT.TXT로 한다.
롤러 코스터를 운행해서 얻을 수 있는 요금을 출력한다.
예제
4 6 4
1 4 2 1
21
로그인해야 코드를 작성할 수 있어요.