Единственное отличие между легкой и сложной версиями — ограничения.
Поликарпу нужно написать курсовую работу. Курсовая работа состоит из \(m\) страниц.
У Поликарпа также есть \(n\) чашек кофе. Кофе в \(i\)-й чашке содержит \(a_i\) кофеина. Поликарп может выпить некоторые чашки кофе (каждую не более одного раза). Он может пить чашки в любом порядке. Поликарп пьет каждую чашку мгновенно и полностью (то есть он не может разделить какую-либо чашку на несколько дней).
Конечно же, курсовые работы не всегда пишутся за один день (по крайней мере в идеальном мире Берляндии). Некоторые из них требуют множества дней упорного труда.
Рассмотрим какой-нибудь день работы Поликарпа. Пусть Поликарп выпил \(k\) чашек кофе, а количества кофеина в чашках, которые Поликарп выпил в течение этого дня, равны \(a_{i_1}, a_{i_2}, \dots, a_{i_k}\). Тогда первая чашка, которую он выпьет, даст ему энергию на написание \(a_{i_1}\) страниц курсовой работы, вторая чашка даст ему энергию на написание \(max(0, a_{i_2} - 1)\) страниц, третья чашка даст ему энергию на написание \(max(0, a_{i_3} - 2)\) страниц, ..., и \(k\)-я чашка даст ему энергию на написание \(max(0, a_{i_k} - k + 1)\) страниц.
Если Поликарп не пьет кофе в течение какого-либо дня, то он вообще не может писать курсовую работу в течение этого дня.
Поликарп хочет закончить курсовую работу настолько рано, насколько это возможно (потратить минимальное количество дней на это). Ваша задача — найти это количество дней или сказать, что это невозможно.
Выходные данные
Если написать курсовую работу невозможно, выведите -1. Иначе выведите минимальное количество дней, необходимое Поликарпу для того, чтобы сделать это.
Примечание
В первом тестовом примере Поликарп может выпить четвертую чашку в течение первого дня (и написать \(1\) страницу), первую и вторую чашки в течение второго дня (и написать \(2 + (3 - 1) = 4\) страницы), пятую чашку в течение третьего дня (и написать \(2\) страницы) и третью чашку в течение четвертого дня (и написать \(1\) страницу), таким образом, ответ равен \(4\). Очевидно, что невозможно написать курсовую за три дня или быстрее.
Во втором тестовом примере Поликарп может выпить третью, четвертую и вторую чашки в течение первого дня (и написать \(4 + (2 - 1) + (3 - 2) = 6\) станиц) и шестую чашку в течение второго дня (и написать \(4\) страницы), таким образом, ответ равен \(2\). Очевидно, что Поликарп не может написать курсовую работу полностью за один день в этом тесте.
В третьем тестовом примере Поликарп может выпить все чашки кофе в течение первого дня и написать \(5 + (5 - 1) + (5 - 2) + (5 - 3) + (5 - 4) = 15\) страниц курсовой работы.
В четвертом тестовом примере Поликарп не может выпить все чашки кофе в течение первого дня и должен выпить одну из них в течение второго дня. Таким образом, В течение первого дня он напишет \(5 + (5 - 1) + (5 - 2) + (5 - 3) = 14\) страниц курсовой работы, а в течение второго дня он напишет \(5\) страниц курсовой работы. Этого достаточно, чтобы завершить ее.
В пятом тестовом примере Поликарп в принципе не может завершить курсовую работу, даже если он будет пить по одной чашке кофе каждый день, поэтому ответ равен -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 8
2 3 1 1 2
|
4
|
|
2
|
7 10
1 3 4 2 1 4 2
|
2
|
|
3
|
5 15
5 5 5 5 5
|
1
|
|
4
|
5 16
5 5 5 5 5
|
2
|
|
5
|
5 26
5 5 5 5 5
|
-1
|