33674번 - 하늘에서 떨어지는 $N$개의 별

문제

당신은 $D$일 동안 하떨별 마을의 환경 관리자로 일하게 되었다. 하떨별 마을은 하늘에서 별이 떨어지기로 유명한 마을로 별들은 다음과 같은 규칙으로 떨어진다.

• 별이 떨어지는 위치는 $N$개의 점이다. 점은 순서대로 1ドル,ドル 2ドル,ドル $\cdots,ドル $N$의 번호를 갖는다.
• 첫날 낮에 모든 점에 쌓인 별의 개수는 각각 0ドル$개다.
• $i$번 점에는 매일 밤 $s_i$개의 별이 떨어진다. $(1 \le i \le N)$

별이 많이 쌓이면 폭발할 수 있기 때문에 쌓인 별을 청소해야 한다.

• 임의의 $i$번 점에 쌓인 별의 개수가 $K$개를 초과하면 해당 점의 별들이 폭발한다. $(1 \le i \le N)$
• 별이 떨어지는 밤이 되기 전, 낮에 청소 작업을 할 수 있다. 청소 작업을 진행하면 모든 점에 쌓인 별이 0ドル$개가 된다.

여러분은 $D$일 동안 떨어진 별이 폭발하지 않게 관리해야 한다. $D$일 동안 별이 폭발하지 않도록 하는 최소 청소 횟수를 구해보자.

입력

첫 번째 줄에 정수 $N,ドル $D,ドル $K$가 공백으로 구분되어 주어진다.

두 번째 줄에 정수 $s_1, s_2, \cdots, s_N$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 $D$일 동안 별이 폭발하지 않도록 할 수 있는 최소 청소 횟수를 출력한다.

제한

• 1ドル \le N, D, K \le 100$
• 1ドル \le s_i \le K$
• 1ドル \le i \le N$

힌트