题目描述

公元 $1888$ 年，江桥和他的 $n - 1$ 个朋友们准备坐船到河的对岸。

岸边只有一条船，江桥可以选择租若干次船。

对于每次租船，船夫都会带至少一个人到河的对岸，然后船夫独自乘船回到初始岸边。

所有乘船的人需要按顺序一个一个上船。由于船年久失修，除船夫外，第 $i$ 个上船的人会使得沉船的风险值增加 $i\times a_i$（无论之前上船的人是否已经下船）。船的风险值一旦超过 $m$，船夫就会立刻将所有人赶下船并不再带任何人去河对岸。只有船夫的船风险值可视为 $0$。

由于江桥的零花钱已经所剩无几，他想请聪明的你来帮他计算一下，在保证他和他的所有朋友都能坐船到达河对岸的前提下，最少要租几次船。

保证至少有一种方式可以使得所有人都到达河对岸。

输入格式

第一行，两个正整数 $n,m$ 表示总人数和风险值参数。

接下来一行 $n$ 个非负整数 $a_i$ ，含义如上所述。

输出格式

一个非负整数，表示答案。

4 19
6 1 4 2

2

3 61174500
32967118 28951401 13248016

3

样例解释

对于第一组样例，上船的顺序为 $6,4,2,1$，其中前两个人一条船，风险值为 $1 \times 6 + 2 \times 4 = 14$，后两个人一条船，风险值为 $3 \times 2 + 4 \times 1 = 10$。因此只需要租两次船。

数据规模与约定

下发文件

下发文件分别对应子任务 $3$、$4$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 18,1 \leq a_i \leq m \leq 10^8$。保证至少有一种方式可以使得所有人都到达河对岸。