# 2973 - Maratona de Pipoca
- **ID**: 2973
- **IdBecrowd**: 2973
- **Tags**: programacao-dinamica
- **Nível**: 9
- **Tempo Limite**: 1 segundos
- **Memória**: 200 MB
- **Categoria**: Paradigmas
- **Autor**: Maratona de Programação 2019, SBC Brazil

## Descrição
A Maratona Brasileira de Comedores de pipocas é uma competição que ocorre anualmente com o intuito de descobrir qual a equipe mais organizada, preparada e bem-treinada na arte de comer pipoca.

Ela é organizada pela SBCp (Sociedade Brasileira de Comedores de pipocas), que periodicamente se reúne para discutir as regras e o formato da competição.

A competição consiste em N sacos de pipocas colocados lado a lado, onde cada saco possui uma quantidade arbitrária de pipoca. Para proporcionar uma maior diversão, a competição ocorre em equipes, cada uma composta por C competidores. Como a Maratona Brasileira de Comedores de pipocas é um evento sério que preza, além de tudo, pela saúde dos competidores, a comissão médica impôs que cada competidor poderá comer, no máximo, T pipocas por segundo, a fim de evitar um possı́vel mal-estar.

A SBCp, em sua última reunião, definiu duas novas regras para a edição de 2019:

Cada competidor da equipe deverá comer uma sequência contı́gua de sacos de pipoca. É perfei- tamente válido que um competidor não coma nenhuma pipoca.

Todas as pipocas de um mesmo saco devem ser comidas por um único competidor.

O objetivo da competição é comer todas as pipocas no menor tempo possı́vel, dado que os C competidores podem comer em paralelo e eles respeitarão todas as regras impostas pela SBCp.

## Entrada
A primeira linha contém três inteiros 
N
, 
C
 e 
T
 (1 ≤ 
N
 ≤ 10
5
, 1 ≤ 
C
 ≤ 10
5
 e 1 ≤ 
T
 ≤ 50), representando a quantidade de sacos de pipoca, a quantidade de competidores de uma mesma equipe e quantidade máxima de pipoca por segundo que um competidor pode comer. A segunda linha conterá 
N
 inteiros 
P
i
 (1 ≤ 
P
i
 ≤ 10 4 ), sendo estes a quantidade de pipoca em cada um dos 
N
 sacos.

## Saída
Seu programa deve produzir uma única linha com um inteiro representando a quantidade mı́nima de segundos necessária para a equipe comer todas as pipocas se ela se organizar da melhor maneira possı́vel.

## Exemplos
### Exemplo de Entrada
```
5 3 4

                                5 8 3 10 7
```

### Exemplo de Saída
```
4
```