D. Амьтад

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 64 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Эрт урьдын цагт өөрийн мэргэжлийн амжилтаараа бусдад танигдсан Дравде хүнд өдрийг даван гэртээ иржээ. Таны санаж байгаачлан тэрээр Огудар-Олок хэмээх архины төрлийн бус, шидэт ундааны агуулахад ажилладаг билээ. Тус өдөр тэрээр 9875 ширхэг хайрцаг ундаа уух хэрэгтэй болсон ба үүнийгээ ууж дуусаад гэртэй ирээд шууд орондоо орон унтжээ.

Дравде хэрхэн амжилттайгаар ферм байгуулах талаар зүүдэлж гэнэ. Түүний зүүдэнд өдөр болгон нэг амьтан түүн дээр ирэн фермдээ нутагшуулахыг гуйж байв. Тэгсэн хэдий ч тэрээр зарим амьтдыг хөөж явуулах буюу өөрийн фермдээ нутагшуулахаас татгалзаж болох юм. Түүний зүүдэнд яг $n$ ширхэг өдөр байсан ба $i$-р өдөр түүний фермд ирсэн амьтан тухайн $i$-р өдрөөс эхлэн өдөр бүр яг $c_{i}$ тонн өвс иддэг байжээ. Гэхдээ хэрэв тухайн амьтан нь ямар нэгэн өдөр өөрийн идэх хэмжээний өвсөө идэж чадахгүй бол маш их гунигладаг байв. Түүний зүүд эхлэхэд Дравде-ийн фермд нийтдээ яг $X$ тонн өвс байжээ.

Дравде үнэхээр айн сэрэв...

Тэрээр танд өөрийн зүүдээ ярьж өгөх гэсэн боловч $n$-р өдөр түүний фермд хэчнээн амьтан байсан болохыг мартжээ. Гэвч тэрээр ямар ч амьтан гуниглаагүй өөрөөр хэлбэл түүний ферм нь нэгэн аз жаргалтай ферм байсан тухай танд хэлж өгөв. Мөн түүний фермд байсан амьтдын тоо нь боломжит хамгийн их байсан болохыг хэлжээ. Түүнчлэн Дравде таныг түүнд туслан ферм дээр байж болох амьтдын боломжит хамгийн их тоог олж өгөхийг хүсэв.

Түүний зүүдэнд амьтад нь өглөө ферм дээр ирдэг бөгөөд Дравде амьтдыг үдээс хойш хооллодог байжээ. Иймд хэрэв тэрээр ямар нэгэн амьтныг фермдээ үлдээхээс татгалзвал тухайн амьтан нь фермийн хоолноос огт идэж чадахгүй гэсэн үг юм. Гэхдээ ямар нэгэн амьтан нь фермд үлдэхээр болсон бол тэрээр $n$-р өдөр хүртэл тогтмол хэмжээний өвсөө идсээр байна.

Оролт

Эхний мөрөнд бүхэл тоонууд $n$ болон $X$ ($1 ≤ n ≤ 100, 1 ≤ X ≤ 10^{4}$) өгөгдөх ба эдгээр нь Дравде-ын зүүд доторх өдрийн тоо болон фермд анх байсан өвсний нийт хэмжээг (тонноор өгөгдөнө) илэрхийлнэ. 2-дахь мөрөнд бүхэл тоонууд $c_{i}$ ($1 ≤ c_{i} ≤ 300$)-ууд өгөгдөнө. 2-дахь мөрөнд өгөгдсөн тоонууд нь зайгаар тусгаарлагдсан байна.

Гаралт

$n$-дэх өдрийн төгсгөлд бүх амьтад нь огт гуниглаагүй өөрөөр хэлбэл бүгдэд нь өгөх өвс хангалттай байх фермийн нийт амьтдын боломжит хамгийн их утгыг хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3 4
1 1 1
Гаралт
2
Оролт
3 6
1 1 1
Гаралт
3

Тэмдэглэл

Эхний жишээг авч үзье: Дравде 2 болон 3-р амьтдыг фермдээ үлдээх юм. 2-р амьтан нь 2-дахь өдөр нэг тонн өвс, 3-дахь өдөр мөн нэг тонн өвс иднэ. Харин 3-р амьтан нь 3-дахь өдөн нэг тонн өвс идэх юм.

Сэтгэгдлүүдийг ачааллаж байна...