Tania 面前有 $$$n$$$ 糖果盒。这些盒子从左到右排成一排,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 个盒子包含 $$$r_i$$$ 糖果,糖果的颜色为 $$$c_i$$$(颜色可以采用三个值之一——红色、绿色或蓝色)。一个盒子里的所有糖果都具有相同的颜色(并且它等于 $$$c_i$$$)。
最初,Tanya 位于箱子编号 $$$s$$$ 旁边。 Tanya 可以移动到相邻的盒子(即数字相差 1)或吃当前盒子中的糖果。坦尼娅立即吃掉糖果,但动作需要一秒钟。
如果坦尼娅吃了盒子里的糖果,那么盒子本身仍然在原地,但里面没有更多的糖果。换句话说,坦尼娅总是吃掉盒子里的所有糖果,并且盒子里的糖果不会再装满。
众所周知,Tanya 不能连续吃掉同一种颜色的糖果(也就是说,她吃糖果的连续两个盒子里的糖果颜色总是不同的)。此外,坦尼娅的胃口不断增长,因此在她吃糖果的下一个盒子中,糖果的数量应该严格比前一个盒子多。
请注意,对于 Tanya 吃糖果的第一个盒子,糖果的颜色和数量没有限制。
Tanya 想要吃至少 $$$k$$$ 糖果。她至少需要多少秒?请记住,她会立即吃掉糖果,时间只花在动作上。
输入
第一行包含三个整数 $$$n$$$、$$$s$$$ 和 $$$k$$$ ($$$1 \le n \le 50$$$、$$$1 \le s \le n$$$、$$$1 \le k \le 2000$$$) — 盒子的数量、Tanya 的初始位置和吃糖果数量的下限。下面一行包含 $$$n$$$ 整数 $$$r_i$$$ ($$$1 \le r_i \le 50$$$) — 盒子里糖果的数量。第三行包含 $$$n$$$ 字母“R”、“G”和“B”序列,表示相应框中糖果的颜色(“R”表示红色,“G”表示绿色,“B”表示蓝色)。回想一下,每个盒子只包含一种颜色的糖果。第三行不包含空格。
输出
打印吃掉至少 $$$k$$$ 糖果的最小秒数。如果解不存在,则打印“-1”。
示例
输入 #1
5 3 10 1 2 3 4 5 RGBRR
输出 #1
4
输入 #2
2 1 15 5 6 RG
输出 #2
-1
注意
第一个示例中 Tanya 的操作顺序:
- 从框$$$3$$$移动到框$$$2$$$;
- 吃盒子里的糖果$$$2$$$;
- 从框$$$2$$$移动到框$$$3$$$;
- 吃盒子里的糖果$$$3$$$;
- 从框$$$3$$$移动到框$$$4$$$;
- 从盒子$$$4$$$移动到盒子$$$5$$$;
- 吃盒子里的糖果$$$5$$$。
由于 Tanya 会立即吃掉糖果,因此所需时间为四秒。