Коров'яче танцювальне шоу#10547
Після кількох місяців репетицій корови вже майже готові представити свій щорічний танцювальний виступ. Цього року вони виконують знаменитий коров'ячий балет «Cowpelia».
Єдине, що залишилося визначити для виступу, — це розмір сцени. Сцена розміру може вмістити одночасно танцюючих корів. Корови в стаді пронумеровані числами 1, \ldots, n у тому порядку, в якому вони повинні виходити на сцену. Кожна корова планує танцювати протягом певного проміжку часу тривалістю .
Спочатку корови 1, \ldots, k виходять на сцену і починають танцювати. Коли перша з цих корів закінчує свою частину, вона залишає сцену, а корова k + 1 негайно починає танцювати. Цей процес продовжується, тож одночасно на сцені завжди танцюють корів (до кінця виступу, коли кількість корів, що залишилися, стає меншою за ).
Виступ закінчується, коли остання корова закінчує свою танцювальну частину, у момент часу .
Очевидно, що чим більше значення , тим менше значення . Оскільки виступ не повинен тривати занадто довго, вам задано обмеження T_{\max} на його тривалість. За цього обмеження визначте мінімально можливе значення .
У першому рядку містяться n~(1 \le n \le 10000) та T_{\max}, де T_{\max} — ціле число, що не перевищує 10^6.
У наступних рядках містяться тривалості d(1), \ldots, d(n) танцювальних частин корів 1, \ldots, n відповідно. Кожне значення є цілим числом у діапазоні 1, \ldots, 10^5.
Гарантується, що при k = n виступ закінчується в межах встановленого обмеження за часом.
Виведіть мінімально можливе значення , при якому танцювальний виступ триває не більше T_{\max} одиниць часу.
Приклад 1