Fewest boats for all passengers

Problem

A college trip goes boating on a lake. Each boat carries at most two students, and their total weight must not be more than L kg. Every student weighs at most L kg, so everyone can travel alone if needed. Print the fewest boats needed to take every student across.

Input, output and limits

Input: The first line has two integers n and L: the number of students and the weight limit. The second line has the n weights, in any order.
Output: One integer: the smallest number of boats.
Constraints: 1 ≤ n ≤ 10^5
1 ≤ weight ≤ L ≤ 3 × 10^9

Examples

Example

Input

5 100
70 50 80 50 30

Output

80 goes alone, 30 goes with 70, and the two 50s share a boat. That is 3 boats.

Hints

Try the problem first. Open one hint at a time.

Hint 1

The heaviest student has the fewest possible partners. Decide that student first.

Hint 2

If the heaviest student cannot share with the lightest one, the heaviest student cannot share with anyone.

Hint 3

Sort the weights. Keep one index at the lightest and one at the heaviest. The heaviest always gets a boat. Add the lightest to it when they fit together.

Hint 4

Stop when the indexes cross. Use long for the weights and the sum.

Write your Java code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More Two Pointer problems

Problem

Input, output and limits

Examples

Hints

More Two Pointer problems