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 i-th 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.

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 space-separated integers a_i (2 ≤ a_i ≤ 2000) — the number of people in the i-th group.

Print the minimum possible number of tables to seat all the friends.

sample input	sample output
3 4 5 6 7	5

sample input	sample output
4 4 3 3 3 3	4

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.