543. Cafe
Time limit per test: 1
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
After competing in a programming contest
n groups of friends have decided to take a rest from problem solving and have come to a cafe. The groups are numbered by integers from 1 to
n, and the
ith group contains
a_{i} friends. The tables in the cafe are absolutely identical, for
r persons each. Now the friends have faced a tricky problem. They want to sit at the tables in such a way that nobody sits alone separately from his or her group. In other words, for each person there should be another person from his/her group sitting at his/her table. There are no other restrictions. People from different groups can sit at the same table. Friends from the same group can sit at different tables. Places at the tables can be left vacant. Your task is to seat all the friends in the described way using the minimum possible number of tables.
Input
The first line of the input contains two integers
n and
r (1 ≤
n ≤ 2000; 3 ≤
r ≤ 2000), where
n is the number of groups, and
r is the number of places at each table. The second line contains
n spaceseparated integers
a_{i} (2 ≤
a_{i} ≤ 2000) — the number of people in the
ith group.
Output
Print the minimum possible number of tables to seat all the friends.
Example(s)
sample input

sample output

3 4
5 6 7

5

sample input

sample output

4 4
3 3 3 3

4

Note
A possible arrangement for the first sample test is:
 table 1: 3 people from the 1st group, 1 empty place;
 table 2: 2 people from the 1st group, 2 people from the 2nd group;
 table 3: 4 people from the 2nd group;
 table 4: 4 people from the 3rd group;
 table 5: 3 people from the 3rd group, 1 empty place.