7503. Olympiad

n teams arrived at Programming Competition, each team consists of a_i (1 ≤ i ≤ n) participants. For competition the classes were prepared with the same number m of computers in each one. Find the minimum number of classes required for competition so that each class will contain participants from different teams only. That is, in any class cannot be more than one participant from one team.

Input. The first line contains the numbers n and m. The second line contains n integers a_i (1 ≤ i ≤ n). All numbers are nonnegative and do not exceed 100.

Output. Print one number – the minimum required number of classes.

Sample input	Sample output
5 3 2 3 4 1 2	4

SOLUTION

loops

Algorithm analysis

In total, s = participants arrived at the competition. Each room contains m computers, then you need at least rooms. Let p be the largest number of participants from one team (the maximum value among all A_i). If p > , then we need at least p rooms. It can be shown that max(, p) classes is always enough for the Olympiad.

Example

There are 2 + 3 + 4 + 1 + 2 = 12 schoolchildren arrived at the Olympiad. Each class has m = 3 computers, so for the Olympiad it is necessary to use at least 12 / 3 = 4 classes.

The maximum number of participants is from the third team, it is 4, that can be seated one by one in 4 classes.

For example, the following arrangement of children is possible.

Algorithm realization

Read the input data.

scanf("%d %d",&n,&m);

Compute the total number of participants s, and the size p of the largest team.

p = 0;

for (i = 0; i < n; i++)

{

scanf("%d",&x);

s += x;

if (x > p) p = x;

}

The value res = compute as (s + m – 1) / m.

res = (s + m - 1) / m;

If p > , the answer will be p.

if (res < p) res = p;

Print the answer.

printf("%d\n",res);