Саша очень любит пить газировку, поэтому у него есть $$$n$$$ бутылок газировки, каждая из которых может вместить любой объем напитка. Изначально в $$$i$$$-й бутылке находится $$$a_i$$$ литров газировки. Саша очень требовательный, поэтому за один глоток он может выпить ровно $$$x$$$ литров из каждой бутылки с произвольного префикса.

Более формально, чтобы сделать один глоток Саша должен выбрать целое число $$$k$$$ ($$$1 \leq k \leq n$$$), а также натуральное число $$$x$$$, такое, что min($$$a_1, \ldots, a_k$$$) $$$\geq x$$$, после чего Саша выпивает по $$$x$$$ литров газировки из первых $$$k$$$ бутылок.

Саша хочет выпить за один глоток хотя бы $$$b$$$ литров. К сожалению, сейчас в бутылках может не хватать газировки для такого глотка, поэтому Саша хочет долить газировку в какие-то бутылки, чтобы он смог сделать глоток хотя бы на $$$b$$$ литров, при этом долив как можно меньше газировки.

Поскольку Саша умеет только лишь пить газировку, он просит вас помочь ему и по данному массиву $$$a$$$ и числу $$$b$$$ посчитать минимальное количество литров, которое нужно долить, чтобы Саша смог сделать глоток на хотя бы $$$b$$$ литров.

В данной задаче 20 тестов, помимо тестов из условия, каждый из них оценивается в 5 баллов.

Решения, корректно работающие при $$$n \le 500$$$, наберут не менее 20 баллов.

Дополнительно решения, корректно работающие, когда все числа $$$a_i$$$ равны, наберут не менее 10 баллов.

Дополнительно решения, корректно работающие, когда $$$a_{i} \leq a_{i+1}$$$ для всех $$$i$$$ (массив неубывающий), наберут не менее 10 баллов.

Дополнительно решения, корректно работающие, когда $$$a_{i+1} \leq a_i$$$ для всех $$$i$$$ (массив невозрастающий), наберут не менее 30 баллов.