Ferris Wheel CSES Solution with Explanation | CSES Problem Set

 

Ferris Wheel

There are n$n$ children who 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$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$n$ and x$x$: the number of children and the maximum allowed weight.

The next line contains n$n$ integers p1,p2,…,pn$p_1,p_2,\dots ,p_n$: the weight of each child.

Output

Print one integer: the minimum number of gondolas.

Constraints

• 1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$
  
• 1≤x≤109$1\le x\le {10}^9$
  
• 1≤pi≤x$1\le p_i\le x$
  

Example

Input:
4 10
7 2 3 9

Output:
3