You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面描述

一个月黑风高的夜晚，博物馆内闯入了一个小偷，小偷想要偷走全部的艺术品！

具体来说，博物馆中有 $N$ 件排列为一排的艺术品，每种艺术品有一个属性值是体积，我们用 $A_i$ 来表示。

不幸的是，小偷的口袋大小只有 $W$ ，所以小偷一次所偷走的所有艺术品的体积之和不能大于 $W$ 。

博物馆的监控有一个奇怪的特性，即小偷必须从 第 $1$ 件艺术品开始偷窃，然后依次是 $2,3,4……$ ，否则监控就会报警。

在不触发警报的前提下，小偷至少需要几次可以偷走全部艺术品？

如果不能全部偷走，输出-1

输入格式

第一行两个正整数 $N$ , $W$ 表示博物馆的艺术品数量，小偷的口袋大小。

接下来输入第 $i$ 个艺术品的体积 $A_i$

输出格式

输出一行一个整数，在不触发警报的前提下，小偷偷走全部艺术品的最小次数。

如果不能全部偷走，输出-1

输入输出样例

input1

3 6
3 4 2

output1

2

input2

4 7
6 1 3 8

output2

-1

说明 / 提示

样例说明

• 第一组数据，最佳选择是第一次拿第一个艺术品，第二次拿第二，三个艺术品
• 无法拿走全部

数据范围

• 对于 $30\%$ 的数据，$1\ \le\ N\ \le\ 10^2$ ， $1\ \le\ A_i,W\ \le\ 5\ \times\ 10^3$
• 对于 $100\%$ 的数据，$1\ \le\ N\ \le\ 3\ \times\ 10^5$，$1\ \le\ A_i,W\ \le\ 3\ \times\ 10^8$