#853. 母鸡下蛋

母鸡下蛋

题目背景

鸡国中的母鸡最擅长下蛋了,MGMG是鸡国中一只以下蛋产量高而闻名全鸡国的母鸡。

题目描述

鸡国中的母鸡最擅长下蛋了,MGMG是鸡国中一只以下蛋产量高而闻名全鸡国的母鸡。鸡国专供下蛋的n个鸡窝呈一字排列在鸡国的"下蛋中心",从左到右依次编号为1到n。每个鸡窝都有一个最大可下蛋的量,其中第i个鸡窝的最大可下蛋量为c_i。有时候由于MGMG产量实在太大而无法在一个鸡窝中下完所有的蛋,不得不转移到隔壁的鸡窝继续下蛋,如果隔壁的鸡窝还是不能让它下完所有的蛋,则MGMG继续转移,直到下完所有的蛋,或者向"下蛋中心"管理员投诉"鸡窝数量实在太少了,我一只鸡的下蛋量都装不下!"。 为了节省转移时所耗费的体力,请你编程帮助MGMG找若干个连续的鸡窝(个数尽量少),让它能下完所有的蛋。

输入格式

输入共2行。 第1行输入两个整数n和t,表示"下蛋中心"有n个可供下蛋的鸡窝,MGMG一次总共要下t个鸡蛋。 第2行n个正整数c_i(1≤i≤n),依次表示第i个鸡窝最大可下蛋量为c_i个。

输出格式

输出1行一个整数或一个单词。当输出整数时表示让MGMG下完所有的蛋至少需要几个连续的鸡窝。当MGMG用完所有的鸡窝都无法下完所有的蛋时,MGMG表示非常愤怒,输出单词"Angry"(不包含双引号,注意大小写)。

样例输入

5 4
1 2 1 2 3

样例输出

2

样例解释

样例1中,有5个鸡窝,可下蛋量分别为1,2,1,2,3。MGMG如果选择第1,2,3号鸡窝能下完4个蛋,但要用3个鸡窝,而选择第4号和第5号鸡窝也能下完4个蛋(还有1个多余的容量),但用到的鸡窝只有2个。 注意:由于第2号和第4号鸡窝不连续,不可以作为选择的方案之一。

数据范围约定

  • 测试点1~6:1≤n≤100,1≤t≤1000,1≤c_i≤100
  • 测试点7~14:1≤n≤10^5,1≤t≤10^8,1≤c_i≤10000
  • 测试点15~20:1≤n≤10^6

提示:本题选择连续鸡窝的方案可能不唯一,但输出的答案是唯一的。