Increase
Турнир за Купата на Декана, 2013
Time Limit: 0.1s, Memory Limit: 64MiB
Ели има списък с N цели числа A1, A2, …, AN. Тя може да си избере някакво цяло число K и към всяко от числата Ai да прибави i * K. Taka А1 става А1 + 1*K, А2 става А2 + 2*K, …, AN става AN + N*K.

Сега момичето се пита колко най-малко трябва да е K, за да съществува отрязък от списъка (тоест един или повече негови последователни елементи), чиято сума е по-голяма или равна на M.

Нека, например, N = 5, M = 21, и първоначалните стойности на числата в списъка са (-5, 4, -13, -3, -7). Така, избирайки K = 3, числата биха станали (-2, 10, -4, 9, 8), като сумата 10 – 4 + 9 + 8 е по-голяма или равна на 21 (числото M). Може да се убедите, че това е и най-малкото K, при което това е възможно. Наистина, при K = 2 числата в списъка стават (-3, 8, -7, 5, 3), като никоя част от него не е по-голяма или равна на 21.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и M – съответно броя числа в списъка и минималната търсена сума. На следващия ред са зададени N на брой цели числа A1, A2, ..., AN – първоначалните стойности на числата в списъка.
Изход
На единствен ред на стандартния изход изведете едно цяло число - минималната стойност на K, която удовлетворява изискването на момичето.
Ограничения
  • 1 ≤ N ≤ 100,000
  • 1 ≤ M ≤ 1,000,000,000
  • -1,000,000 ≤ Ai ≤ 1,000,000
Примерен Вход Примерен Изход
5 21 -5 4 -13 -3 -7 3
10 42 5 17 -4 13 0 0 21 17 11 19 -1
Забележете, че отговорът може да бъде и отрицателен.
Мрън!