Перед Таней расположены \(n\) коробок с конфетами. Коробки расположены в ряд слева направо, пронумерованы от \(1\) до \(n\). В \(i\)-й коробке находится \(r_i\) конфет, конфеты имеют цвет \(c_i\) (цвет может принимать одно из трёх значений — красный, зеленый или синий). Все конфеты внутри одной коробки имеют одинаковый цвет (и он равен \(c_i\)).
Изначально Таня находится рядом с коробкой номер \(s\). Таня может переместиться к соседней коробке (то есть с номером, который отличается на единицу) или съесть конфеты в этой коробке. Конфеты Таня съедает мгновенно, а вот перемещение занимает одну секунду.
Если Таня съедает конфеты из коробки, то сама коробка остаётся на своём месте, но конфет в ней больше нет. Иными словами, Таня всегда съедает все конфеты из коробки и конфеты в коробках не восполняются.
Известно, что Таня не позволяет себе съедать подряд конфеты одинакового цвета (то есть цвета конфет в двух последовательных коробках, из которых она съедает конфеты — всегда различны). Кроме того, аппетит Тани постоянно растёт (она и сама постоянно растёт), поэтому в каждой следующей коробке, из которой она съедает конфеты, должно быть строго больше конфет, чем в предыдущей.
Заметим, что для первой коробке, откуда Таня съест конфеты, ограничений на цвет и количество конфет — нет.
Таня хочет съесть не менее \(k\) конфет. Какое минимальное количество секунд ей потребуется? Помните, что конфеты она съедает моментально, а время тратится только на перемещения.
Выходные данные
Выведите одно целое число — наименьшее необходимое время для того, чтобы Таня съела не менее \(k\) конфет. Если решения не существует, выведите «-1».
Примечание
Последовательность действий Тани для первого примера:
- переместиться от коробки \(3\) к коробке \(2\);
- съесть конфеты в коробке \(2\);
- переместиться от коробки \(2\) к коробке \(3\);
- съесть конфеты в коробке \(3\);
- переместиться от коробки \(3\) к коробке \(4\);
- переместиться от коробки \(4\) к коробке \(5\);
- съесть конфеты в коробке \(5\).
Так как конфеты Таня ест мгновенно, необходимое время — четыре секунды.