题目描述

在遥远的“星辰群岛”上，有一个被誉为“宝石馆”的宝库，这里收藏了N件珍贵的宝石，每颗宝石都有一个属性值表示其大小，用 $𝐴_𝑖$ 来表示。

然而，不幸的是，一群狡猾的盗贼“影贼”悄悄地潜入了宝石馆，他们企图偷走这些珍贵的宝石。影贼们携带的包裹大小有限，只有 𝑊 大小（由于他们资源有限，只能携带小包裹），因此他们一次所能偷走的所有宝石的总大小不能超过 𝑊。

宝石馆的安保系统拥有一个独特的特性：只有按照顺序从第一个宝石开始取，2、3、4……依次进行，否则安保系统就会触发警报。

在不触发警报的前提下，影贼们至少需要几次才能偷走所有的宝石？如果不能全部偷走，他们将面临失败,要输出-1。

输入格式：

第一行两个正整数 𝑁 , 𝑊表示宝石馆的宝石数量和影贼的背包大小。

接下来输入第 𝑖个宝石的体积 $𝐴_𝑖$

输出格式：

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

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

样例：

3 6
3 4 2

2

提示

样例输入2: 4 7 6 1 3 8 样例输出2: -1

• 对于 30% 的数据，1≤𝑁≤$10^2$ ， 1≤𝐴𝑖,𝑊≤5×$10^3$,1≤$A_i$,W≤5×$10^3$
• 对于 100%的数据，1≤𝑁≤3×$10^5$,1≤ N≤3×$10^5$，1≤𝐴𝑖,𝑊≤3×$10^8$,1≤ $A_i$,W≤3×$10^8$