Some children want to go to a Ferris wheel, and your task is to find a gondola for each child.

Each gondola may have one or two children in it, and in addition, the total weight in a gondola may not exceed x. You know the weight of every child.

What is the minimum number of gondolas needed for the children?

Input

The first input line contains two integers N and x: the number of children and the maximum allowed weight.

The next line contains n integers p1,p2,…,pnp_1,p_2,p_np1​,p2​,…,pn​: the weight of each child.

Output

Print one integer: the minimum number of gondolas.

Constraints

• 1≤n≤2⋅1051

• 1≤x≤1091

• 1≤pi≤x1

Example

Input:

4 10
7 2 3 9

Output:

3

To solve this problem, we need to find the maximum number of pairs having a sum less than equal to x and that will give us our answer.

Let's see how we can do this

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,x;
    cin >> n >> x;
    vector<int>p(n);
    for(int i=0;i<n;i++)cin >> p[i];

    sort(p.begin(), p.end());

    int i = 0, j = n-1;
    while(i <= j){ 
        if(i == j){
              if(v[i] <= x){
                   ans++;
                   i++;
                   j--;
             }else if(v[i] + v[j] > x)ans++, j--;
             else if(v[i] + v[j] <= x)ans++, j--, i++;

        }

    }

cout << ans;
}

So, in this fashion we can solve this problem and that's all for this blog ,will seee you in the next one.