Evacuation trucks
After transferring several broken cars from a faraway country with a ferry, they arrived in a neighboring city. Now it’s time to transfer them to the capital. As they are broken, they can only be transferred by evacuation trucks.
It’s known that it’s possible to fit two cars in one evacuation truck if they are light enough - if the sum of their weights does not exceed a certain threshold. Otherwise, each car needs to be transferred with a dedicated evacuation truck.
You are given
n cars with their weights and a threshold evacuation truck can handle. You are asked to calculate the minimum number of evacuation trucks needed to transfer all the cars.Input
The first line of the input contains two integers
n (2 ≤ n ≤ ) and t (1 ≤ t ≤ ) - the number of cars and the maximum weight threshold evacuation trucks can handle.The next line contains
n space separated integers (1 ≤ ≤ t) the weights of the cars.Output
The program should print the minimal number of evacuation trucks needed to transfer all the cars.
Examples
Input | Output |
4 11
5 8 10 2 | 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB