beecrowd | 2973

Maratona Brasileira de Popcorn

By Maratona de Programação 2019, SBC BR Brazil

Timelimit: 1

The “Maratona Brasileira de Popcorn” is a competition that takes place annually to find out which team is the most organized, prepared and well-trained in the art of eating popcorn. It is organized by Brazilian Society of Popcorn Eaters (SBCp, its acronym in Portuguese), which periodically meets to discuss the rules and format of the competition.

The competition consists of N popcorn bags placed side by side, where each bag has an arbitrary amount of popcorn. For added fun, the competition takes place in teams, each made up of C competitors. Since the “Maratona Brasileira de Popcorn” is a serious event that values, above all, the health of the competitors, the medical commission has imposed that each competitor may eat a maximum of T popcorn per second to avoid possible sickness.

At its last meeting, SBCp defined two new rules for the 2019 edition:

The goal of the competition is to eat all the popcorn in the shortest possible time as the C competitors can eat in parallel and they will abide by all rules imposed by the SBCp.

Input

The first line of input contains three integer numbers N , C and T (1 ≤ N ≤ 105 , 1 ≤ C ≤ 105 and 1 ≤ T ≤ 50), representing the number of popcorn bags in the competition, the number of competitors in the team, and the maximum amount of popcorn per second a competitor can eat. The second line contains N integers Pi (1 ≤ Pi ≤ 104), representing the amount of popcorn on each of the N popcorn bags.

Output

Your program must output a single line, containing an integer number, representing The minimum amount of seconds it takes for the team to eat all the popcorn if they organize themselves as best possible.

Input Samples Output Samples

5 3 4
5 8 3 10 7

4

3 2 1
1 5 1

6

3 2 1
1 1 5

5