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
ncars 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.
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
nspace separated integers (1 ≤ ≤ t) the weights of the cars.
The program should print the minimal number of evacuation trucks needed to transfer all the cars.
4 11 5 8 10 2
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB