描述

有 $n$ 个一维物品需要装入相同的箱子中。所有箱子都有完全相同的长度 $l$，并且每个物品 $i$ 的长度 $l_i \leq l$。我们要寻找最小的箱子数 $q$，使得：

• 每个箱子最多包含 $2$ 个物品；
• 每个物品都被装入 $q$ 个箱子中的一个；
• 装入一个箱子中的物品长度之和不超过 $l$。
  给定整数值 $n$，$l$，$l_1$，…，$l_n$，要求你计算出最优的箱子数 $q$。

输入

输入的第一行包含物品的数量 $n$（$1 \leq n \leq 10^5$）。第二行包含一个整数，表示箱子的长度 $l \leq 10000$。然后有 $n$ 行，每行包含一个整数值，表示物品的长度。

输出

你的程序必须输出装入所有物品所需的最小箱子数。

输入示例

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

输出示例

6  

提示

示例实例和一个最优解如下图所示。物品按照输入顺序从 $1$ 到 $10$ 编号。

来源

2005 年西南欧洲