There are N children that want to go to a ferris wheel and you need to allocate passenger cabin for each one.In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of November 2nd
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #04 exercise sheet]
There are N children that want to go to a ferris wheel and you need to allocate passenger cabin for each one.
You know the weight Wi of each child and you know the maximum total weight K of a single cabin. You also know that each cabin can take at most two children (but it might also just take one), as long the total weight on it does not exceed K.
What is the minimum number of cabins you need for all the children?
Given a set of N children and their weights, and also the weight capacity of each cabin in the ferris wheel, your task is to find the minimum number of cabins needed to transport all the children.
The first input line contains two integers N (the amount of children) and K (the maximum weight on a single cabin).
The second line contains N space separated integers indicating the weight of each child.
The output should be a single line containing the minimum number of cabins needed.
The following limits are guaranteed in all the test cases that will be given to your program:
| 1 ≤ N ≤ 2 × 105 | Number of children | |
| 1 ≤ K ≤ 109 | Maximum weight in a cabin | |
| 1 ≤ Wi ≤ K | Weight of each child |
| Example Input 1 | Example Output 1 |
8 10 8 2 9 3 1 6 8 4 |
5 |
We could use for instance the following 5 cabins: (1,9) (2,8) (3,6) (4) (8)
| Example Input 2 | Example Output 2 |
8 11 8 2 9 3 1 6 8 4 |
4 |
We could use for instance the following 4 cabins: (1,9) (2,8) (3,8) (4,6)