C. Таня и цветные конфеты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перед Таней расположены $$$n$$$ коробок с конфетами. Коробки расположены в ряд слева направо, пронумерованы от $$$1$$$ до $$$n$$$. В $$$i$$$-й коробке находится $$$r_i$$$ конфет, конфеты имеют цвет $$$c_i$$$ (цвет может принимать одно из трёх значений — красный, зеленый или синий). Все конфеты внутри одной коробки имеют одинаковый цвет (и он равен $$$c_i$$$).

Изначально Таня находится рядом с коробкой номер $$$s$$$. Таня может переместиться к соседней коробке (то есть с номером, который отличается на единицу) или съесть конфеты в этой коробке. Конфеты Таня съедает мгновенно, а вот перемещение занимает одну секунду.

Если Таня съедает конфеты из коробки, то сама коробка остаётся на своём месте, но конфет в ней больше нет. Иными словами, Таня всегда съедает все конфеты из коробки и конфеты в коробках не восполняются.

Известно, что Таня не позволяет себе съедать подряд конфеты одинакового цвета (то есть цвета конфет в двух последовательных коробках, из которых она съедает конфеты — всегда различны). Кроме того, аппетит Тани постоянно растёт (она и сама постоянно растёт), поэтому в каждой следующей коробке, из которой она съедает конфеты, должно быть строго больше конфет, чем в предыдущей.

Заметим, что для первой коробке, откуда Таня съест конфеты, ограничений на цвет и количество конфет — нет.

Таня хочет съесть не менее $$$k$$$ конфет. Какое минимальное количество секунд ей потребуется? Помните, что конфеты она съедает моментально, а время тратится только на перемещения.

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

В первой строке записаны три целых числа $$$n$$$, $$$s$$$ и $$$k$$$ ($$$1 \le n \le 50$$$, $$$1 \le s \le n$$$, $$$1 \le k \le 2000$$$) — количество коробок, начальное положение Тани и количество конфет, не менее скольки Таня хочет съесть. Следующая строка содержит $$$n$$$ целых числе $$$r_i$$$ ($$$1 \le r_i \le 50$$$) — количества конфет в коробках. Третья строка содержит последовательность из $$$n$$$ символов «R», «G» или «B», которые обозначают цвета конфет в соответствующих коробках («R» — красный, «G» — зеленый, «B» — голубой). Напомним, что каждая коробка содержит конфеты только одного цвета. Третья строка не содержит пробелов.

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

Выведите одно целое число — наименьшее необходимое время для того, чтобы Таня съела не менее $$$k$$$ конфет. Если решения не существует, выведите «-1».

Примеры
Входные данные
5 3 10
1 2 3 4 5
RGBRR
Выходные данные
4
Входные данные
2 1 15
5 6
RG
Выходные данные
-1
Примечание

Последовательность действий Тани для первого примера:

  • переместиться от коробки $$$3$$$ к коробке $$$2$$$;
  • съесть конфеты в коробке $$$2$$$;
  • переместиться от коробки $$$2$$$ к коробке $$$3$$$;
  • съесть конфеты в коробке $$$3$$$;
  • переместиться от коробки $$$3$$$ к коробке $$$4$$$;
  • переместиться от коробки $$$4$$$ к коробке $$$5$$$;
  • съесть конфеты в коробке $$$5$$$.

Так как конфеты Таня ест мгновенно, необходимое время — четыре секунды.