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 addition, the total weight of 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,…,pn,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

Let's understand the problem, the total weight of the gondola cannot exceed x, so to solve this problem, we need to count the maximum number of pairs in the array having a sum less than equal to x.

We need to count the actual number of pairs which has a sum less than or equal to x and we need to actually count the number of pairs which has a sum equal to or less than x.

Let's see how we can do so.

All we have to do is to use the 2-pointer approach in which we have one pointer at the start and another pointer at the end of the given array.

So, we need to just take the sum of these two numbers such that the sum of these two numbers does not exceed x.

Let's jump to the code implementation part.

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

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

    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++;
                  i++;
                  j--;
        }
    }

     cout << ans;
}

Let's understand the code above, we have an array v for which we have to find the number of pairs having a sum not exceeding x.

To solve this problem, we are using 2 pointers i and j where the first points to the first value of the integer and the second to the last value of the integer.

We need