Lets define the weight of any non-empty multi-set of integers as follows:

• If the set has a single element, then its weight is just the value of that element. e.g. weight of {2} is 2.

• Otherwise its weight is the maximum among sum of the two integers in all possible pairs of integers in it. e.g. weight of {1,5,2} will be (2+5) = 7, since this is the maximum sum of integers among all possible pairs (1,5) = 6, (1,2) = 3, (5,2) = 7.

You are given an array of integers of size n and an integer k. You have to divide the elements of the array in minimum number of subsets such that the weight of each subset is at most k. Each element of the array should belong to exactly one subset. Print this minimum possible number of subsets.

Function Description

Complete the optimalPartition function in the editor below. It has the following parameter(s):

Constraints

• 1 ≤ n ≤ 10^5

• 1 ≤ k ≤ 10^8

• 1 ≤ a[i] ≤ k

Input Format 

The first line contains an integer, n, denoting the number of elements in a.

The next line contains an integer, k, denoting the maximum possible weight of each subset.

Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer describing ai.

Note - Use Fast Input/Output Methods for Big Test Cases.