브라질 팝콘 마라톤

브라질 팝콘 마라톤(Maratona Brasileira de Popcorn)은 팝콘 먹기 기술에서 가장 조직적이고 준비가 잘 되어 있으며 훈련이 잘 된 팀을 가리는 대회로, 매년 열린다. 브라질 팝콘 먹는 사람 협회(SBCp)가 주최하며, 협회는 정기적으로 모여 대회의 규칙과 형식을 논의한다.

대회에는 N개의 팝콘 봉지가 나란히 놓여 있고, 각 봉지에는 임의의 양의 팝콘이 들어 있다. 재미를 더하기 위해 대회는 팀 단위로 진행되며, 각 팀은 C명의 참가자로 구성된다. 브라질 팝콘 마라톤은 무엇보다 참가자의 건강을 중시하는 진지한 행사이므로, 의료 위원회는 참가자가 질병에 걸리지 않도록 각 참가자가 1초에 최대 T개의 팝콘만 먹을 수 있다고 규정했다.

지난 회의에서 SBCp는 2019년 대회를 위해 두 가지 새 규칙을 정했다.

• 각 팀 참가자는 연속된 팝콘 봉지 구간을 먹어야 한다. 참가자가 팝콘을 전혀 먹지 않는 것도 완전히 허용된다.
• 같은 봉지에 있는 팝콘은 반드시 한 명의 참가자가 모두 먹어야 한다.

대회의 목표는 C명의 참가자가 동시에 먹을 수 있고 SBCp가 정한 모든 규칙을 지킨다는 전제에서, 모든 팝콘을 가능한 한 짧은 시간 안에 먹는 것이다.

첫째 줄에 정수 N, C, T가 주어진다. (1 ≤ N ≤ 10^5, 1 ≤ C ≤ 10^5, 1 ≤ T ≤ 50) N은 대회의 팝콘 봉지 수, C는 팀의 참가자 수, T는 참가자가 1초에 먹을 수 있는 팝콘의 최대량이다. 둘째 줄에 N개의 정수 P_i가 주어진다. (1 ≤ P_i ≤ 10^4) P_i는 N개의 팝콘 봉지 각각에 들어 있는 팝콘의 양이다.

팀이 최선의 방식으로 역할을 나누었을 때 모든 팝콘을 먹는 데 걸리는 최소 시간(초)을 나타내는 정수 하나를 한 줄에 출력한다.