403043: GYM100981 A Программист 80-го уровня

A. Программист 80-го уровняограничение по времени на тест1 секундаограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Василий мечтает стать программистом k-го уровня. У него есть n дней чтобы осуществить задуманное — повысить свой уровень с 1-го до k-го. Для перехода с уровня x на уровень x + 1 необходимо с момента получения уровня x решить x задач.

В i-й день на одном известном сайте публикуются a_i задач, при этом все они доступны для решения только в день публикации. Каждый день Василий решает задачи последовательно, одну за одной, при этом в i-й день он может решить не больше чем a_i задач. Как только суммарное количество задач, решённых Василием с момента получения последнего уровня x, становится равно x, он останавливается и в этот день больше задач не решает. В этом случае в конце дня он совершает переход на следующий уровень x + 1. При этом задачи, которые Василий в этот день решить не успел, он не решит уже никогда.

Решённые задачи не накапливаются при переходе на следующий уровень, то есть для каждого x для перехода на уровень x + 1 Василию надо решить x задач, именно будучи программистом уровня x.

Василий может приступить к занятиям в любой день от 1 до n, при этом он хочет минимизировать разницу между номером дня, когда он станет программистом k-го уровня, и днём, когда он начнёт заниматься.

Входные данные

В первой строке входных данных записаны два целых числа n и k (1 ≤ n ≤ 500, 2 ≤ k ≤ n + 1) — общее количество дней и уровень, которого Василий хочет достичь, соответственно.

Во второй строке находятся n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 500), где a_i равно количеству доступных для решения задач в i-й день.

Выходные данные

Выведите единственное целое число — минимальное количество дней, в течение которых Василий сможет достичь k-го уровня программирования.

Если достичь желаемого Василию не удастся, выведите -1.

ПримерыВходные данные

6 4
2 2 2 1 3 3

Выходные данные

3

Входные данные

12 5
1 1 1 1 1 1 1 1 1 1 1 1

Выходные данные

10

Входные данные

10 5
10 10 10 10 10 10 10 10 10 10

Выходные данные

4

Примечание

В первом примере Василий может приступить к занятиям в 4-й день:

• в 4-й день решить одну задачу и в конце дня перейти на уровень 2;
• в 5-й день решить две задачи из трёх и в конце дня перейти на уровень 3;
• в 6-й день решить все три задачи и в конце дня перейти на уровень 4.

Во втором примере Василию для перехода на 5-й уровень надо решить 1 + 2 + 3 + 4 = 10 задач. Так как каждый день он может решать не более одной задачи, ему понадобится 10 дней.

В третьем примере Василий может повышать уровень каждый день. Следовательно, ему достаточно 4-х дней.