305578: CF1057C. Tanya and Colored Candies

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Tanya and Colored Candies

题意翻译

妹子sky有 $n$ 个盛小裙子的箱子,第 $i$ 个箱子里有 $r_i$ 件小裙子,每个箱子的颜色是红‘R’,蓝'B',绿'G'的一种。 sky移动缓慢,到旁边的箱子需要 $1$ 的时间,却能立刻穿小裙子,不花费时间。 众所周知,sky还有两个奇怪的要求,她不会连续穿两个箱子颜色相同的裙子,并且每次穿的箱子的小裙子都应该比前一个箱子的小裙子多。 sky马上去参加PSC,要穿**至少** $k$ 件小裙子,现在在第 $s$ 个箱子旁,但是她现在不知道怎么穿能用最少时间,请你告诉她。 注意:对于sky穿小裙子的第一个箱子,颜色和数量没有限制。

题目描述

There are $ n $ candy boxes in front of Tania. The boxes are arranged in a row from left to right, numbered from $ 1 $ to $ n $ . The $ i $ -th box contains $ r_i $ candies, candies have the color $ c_i $ (the color can take one of three values ​​— red, green, or blue). All candies inside a single box have the same color (and it is equal to $ c_i $ ). Initially, Tanya is next to the box number $ s $ . Tanya can move to the neighbor box (that is, with a number that differs by one) or eat candies in the current box. Tanya eats candies instantly, but the movement takes one second. If Tanya eats candies from the box, then the box itself remains in place, but there is no more candies in it. In other words, Tanya always eats all the candies from the box and candies in the boxes are not refilled. It is known that Tanya cannot eat candies of the same color one after another (that is, the colors of candies in two consecutive boxes from which she eats candies are always different). In addition, Tanya's appetite is constantly growing, so in each next box from which she eats candies, there should be strictly more candies than in the previous one. Note that for the first box from which Tanya will eat candies, there are no restrictions on the color and number of candies. Tanya wants to eat at least $ k $ candies. What is the minimum number of seconds she will need? Remember that she eats candies instantly, and time is spent only on movements.

输入输出格式

输入格式


The first line contains three integers $ n $ , $ s $ and $ k $ ( $ 1 \le n \le 50 $ , $ 1 \le s \le n $ , $ 1 \le k \le 2000 $ ) — number of the boxes, initial position of Tanya and lower bound on number of candies to eat. The following line contains $ n $ integers $ r_i $ ( $ 1 \le r_i \le 50 $ ) — numbers of candies in the boxes. The third line contains sequence of $ n $ letters 'R', 'G' and 'B', meaning the colors of candies in the correspondent boxes ('R' for red, 'G' for green, 'B' for blue). Recall that each box contains candies of only one color. The third line contains no spaces.

输出格式


Print minimal number of seconds to eat at least $ k $ candies. If solution doesn't exist, print "-1".

输入输出样例

输入样例 #1

5 3 10
1 2 3 4 5
RGBRR

输出样例 #1

4

输入样例 #2

2 1 15
5 6
RG

输出样例 #2

-1

说明

The sequence of actions of Tanya for the first example: - move from the box $ 3 $ to the box $ 2 $ ; - eat candies from the box $ 2 $ ; - move from the box $ 2 $ to the box $ 3 $ ; - eat candy from the box $ 3 $ ; - move from the box $ 3 $ to the box $ 4 $ ; - move from the box $ 4 $ to the box $ 5 $ ; - eat candies from the box $ 5 $ . Since Tanya eats candy instantly, the required time is four seconds.

Input

题意翻译

妹子sky有 $n$ 个盛小裙子的箱子,第 $i$ 个箱子里有 $r_i$ 件小裙子,每个箱子的颜色是红‘R’,蓝'B',绿'G'的一种。 sky移动缓慢,到旁边的箱子需要 $1$ 的时间,却能立刻穿小裙子,不花费时间。 众所周知,sky还有两个奇怪的要求,她不会连续穿两个箱子颜色相同的裙子,并且每次穿的箱子的小裙子都应该比前一个箱子的小裙子多。 sky马上去参加PSC,要穿**至少** $k$ 件小裙子,现在在第 $s$ 个箱子旁,但是她现在不知道怎么穿能用最少时间,请你告诉她。 注意:对于sky穿小裙子的第一个箱子,颜色和数量没有限制。

加入题单

上一题 下一题 算法标签: