Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Bin Packing
 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 6539 Accepted: 2947

Description

A set of n 1-dimensional items have to be packed in identical bins. All bins have exactly the same length l and each item i has length li<=l . We look for a minimal number of bins q such that
• each bin contains at most 2 items,
• each item is packed in one of the q bins,
• the sum of the lengths of the items packed in a bin does not exceed l .

You are requested, given the integer values n , l , l1 , ..., ln , to compute the optimal number of bins q .

Input

The first line of the input contains the number of items n (1<=n<=105) . The second line contains one integer that corresponds to the bin length l<=10000 . We then have n lines containing one integer value that represents the length of the items.

Output

Your program has to write the minimal number of bins required to pack all items.

Sample Input

```10
80
70
15
30
35
10
80
20
35
10
30
```

Sample Output

```6
```

Hint

The sample instance and an optimal solution is shown in the figure below. Items are numbered from 1 to 10 according to the input order.

Source

[Submit]   [Go Back]   [Status]   [Discuss]