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.


-----Input-----

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.


-----Output-----

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


-----Examples-----
Input
5 3 10
1 2 3 4 5
RGBRR

Output
4

Input
2 1 15
5 6
RG

Output
-1



-----Note-----

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.

Difficulty: interview

Starter code:

Solutions:
n, s, k = list(map(int, input().split()))
amounts = list(map(int, input().split()))
colors = list(input())

dp = [[-1 for j in range(k + 1)] for i in range(n)]

def getAns(nth, left):
    if left <= 0:
        return 0
    if dp[nth][left] >= 0:
        return dp[nth][left]
    
    ret = 999999999
    for i in range(n):
        if amounts[i] <= amounts[nth] or colors[i] == colors[nth]:
            continue
        ret = min(ret, abs(nth - i) + getAns(i, left - amounts[i]))
    
    dp[nth][left] = ret
    return ret

ans = 999999999
for i in range(n):
    ans = min(ans, getAns(i, k - amounts[i]) + abs(s - 1 - i))
if ans == 999999999:
	ans = -1
print(ans)
        


import sys

def minp():
	return sys.stdin.readline().strip()

dp = [None]*50
for j in range(50):
	dp[j] = [None]*2001

n,s,k = list(map(int,minp().split()))
a = [None]*n
i = 0
s -= 1
for j in map(int,minp().split()):
	a[i] = (j, i)
	i += 1
i = 0
for j in minp():
	a[i] += ("RGB".find(j),)
	i += 1
a.sort()
r = 10**18
zzz = 0
for i in range(n):
	ii = dp[i]
	c = a[i][0]
	ii[c] = abs(s-a[i][1])
	#print(ii[c])
	for j in range(i):
		if a[j][2] == a[i][2] or a[j][0] == a[i][0]:
			continue
		jj = dp[j]
		for z in range(2001-c):
			zz = jj[z]
			if zz != None:
				d = zz + abs(a[i][1]-a[j][1])
				cc = z+c
				if ii[cc] != None:
					if ii[cc] > d:
						ii[cc] = d
				else:
					ii[cc] = d
	for z in range(k,2001):
		if ii[z] != None:
			r = min(r,ii[z])
	#print(ii[:k+1])
if r != 10**18:
	print(r)
else:
	print(-1)


INF = 1e10
max_n = 50
max_k = 2000
def main():
    n, s, k = map(int, input().split())
    s -= 1
    buf = ['']*(max_n + 1)
    dp = [[0 for i in range(max_n + 1)] for j in range(max_k + 1)] 
    r = list(map(int, input().split()))
    c = input()
    answer = INF
    for i in range(len(c)):
        buf[i] = c[i]
    for i in range(k, -1, -1):
        for j in range(n):
            dp[i][j] = INF
    for j in range(n):
        value = abs(j - s)
        if k - r[j] <= 0:
            answer = min(answer, value)
        else:
            dp[k - r[j]][j] = value
    for i in range(k, 0, -1):
        for j in range(n):
            if dp[i][j] < INF:
                for l in range(n):
                    if buf[j] != buf[l] and r[j] < r[l]:
                        value = dp[i][j] + abs(j - l)
                        if i - r[l] <= 0:
                            answer = min(answer, value)
                        else:
                            dp[i - r[l]][l] = min(dp[i - r[l]][l], value)
    if answer == INF:
        print(-1)
        return
    print(answer)

def __starting_point():
    main()
__starting_point()

INF = 10e9
n,s,k = list(map(int, input().split()))
r = list(map(int, input().split()))
r.append(0)
col = input()
mat = []
for i in range(n+1):
    adj = {}
    for j in range(n):
        if i == n:
            adj[j] = abs((s-1)-j)
        else:
            if col[i] != col[j] and r[i] < r[j]:
                adj[j] = abs(i-j)
    mat.append(adj)
# print(*mat, sep='\n')

mem = [{} for i in range(n+1)]
# print(mem)

def get(s, k):
    # print(s,k)
    # print(mem)
    if mem[s].get(k):
        return mem[s].get(k)
    if r[s] >= k:
        mem[s][k] = 0
    else:
        mi = None
        for nei in mat[s]:
            ncost = get(nei, k-r[s])
            if ncost is None:
                continue
            curr = ncost + mat[s][nei]
            if mi is None or curr < mi:
                mi = curr
        if mi is not None:
            mem[s][k] = mi
        else:
            mem[s][k] = INF
    return mem[s].get(k)

# print(mem)

ans = get(n,k)
if ans is None or ans >= INF:
    print(-1)
else:
    print(ans)


INF = 10e9
n,s,k = list(map(int, input().split()))
r = list(map(int, input().split()))
r.append(0)
col = input()
mat = []
for i in range(n+1):
    adj = {}
    for j in range(n):
        if i == n:
            adj[j] = abs((s-1)-j)
        else:
            if col[i] != col[j] and r[i] < r[j]:
                adj[j] = abs(i-j)
    mat.append(adj)
# print(*mat, sep='\n')

mem = [{} for i in range(n+1)]
# print(mem)

def get(s, k):
    # print(s,k)
    # print(mem)
    if mem[s].get(k):
        return mem[s].get(k)
    if r[s] >= k:
        mem[s][k] = 0
    else:
        mi = None
        for nei in mat[s]:
            ncost = get(nei, k-r[s])
            if ncost is None:
                continue
            curr = ncost + mat[s][nei]
            if mi is None or curr < mi:
                mi = curr
        if mi is not None:
            mem[s][k] = mi
        else:
            mem[s][k] = INF
    return mem[s].get(k)

# print(mem)

ans = get(n,k)
if ans is None or ans >= INF:
    print(-1)
else:
    print(ans)


inf = 10000
n, s, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(input())
for i in range(n):
    if b[i] == 'R':
        b[i] = 0
    elif b[i] == 'G':
        b[i] = 1
    else:
        b[i] = 2
boxes = [[a[i], b[i], i] for i in range(n)]
boxes.sort()
l = boxes[-1][0] * n + 1
s -= 1
dp = [[[inf, s, -1] for j in range(l)] for i in range(3)]
if l < k:
    print(-1)
    return
dp[0][0][0] = 0
dp[1][0][0] = 0
dp[2][0][0] = 0
for i in range(n):
    pos = boxes[i][2]
    clr = boxes[i][1]
    cnt = boxes[i][0]
    for j in range(l - cnt):
        for c in range(3):
            if c == clr:
                continue
            if dp[clr][j + cnt][0] > dp[c][j][0] + abs(dp[c][j][1] - pos) and cnt > dp[c][j][2]:
                dp[clr][j + cnt][0] = dp[c][j][0] + abs(dp[c][j][1] - pos)
                dp[clr][j + cnt][1] = pos
                dp[clr][j + cnt][2] = cnt
ans = min(dp[0][k][0], min(dp[1][k][0], dp[2][k][0]))
for i in range(k, l):
    ans = min(min(ans, dp[0][i][0]), min(dp[1][i][0], dp[2][i][0]))
if ans < inf:
    print(ans)
else:
    print(-1)

INF = 100000

n,s,k=list(map(int,input().split()))
r = list(map(int,input().split()))
c = input().rstrip()
#dp[i][j]: i = the current position just after eating candies, j = remaining candies to eat
dp = [[INF for j in range(k+1)] for i in range(n)]
s -= 1
for i in range(n):
    dp[i][k-r[i]] = abs(s-i)
for j in range(k,-1,-1):
    for i in range(n):
        if dp[i][j] >= INF: continue
        for f in range(n):
            if r[f] <= r[i]: continue
            if c[f] == c[i]: continue
            new_val = max(0, j-r[f])
            dp[f][new_val] = min(dp[f][new_val], dp[i][j] + abs(i-f))
ans = INF
for i in range(n):
    ans = min(ans, dp[i][0])
if ans >= INF:
    ans = -1

print(ans)


n, s, k = map(int, input().split())
s -= 1
r = list(map(int, input().split()))
INF = float("inf")
c = input()
dp = [[] for i in range(n)]


def calc(u):
    if dp[u]:
        return
    dp[u] = [0] * (r[u] + 1) + [INF] * (k - r[u])
    for i in range(n):
        if c[u] != c[i] and r[i] > r[u]:
            calc(i)
            d = abs(u - i)
            for j in range(r[u] + 1, k + 1):
                dp[u][j] = min(dp[u][j], dp[i][j - r[u]] + d)


ans = INF
for i in range(n):
    calc(i)
    ans = min(ans, abs(i - s) + dp[i][k])
if ans == INF:
    print(-1)
else:
    print(ans)

n,s,k=map(int,input().split())
r=list(map(int,input().split()))
s-=1
c=input()
best=[[0 for i in range(n)] for j in range(k+1)]
for i in range(1,k+1):
    for j in range(n):
        if i<=r[j]:
            best[i][j]=abs(j-s)
        else:
            good=float("inf")
            for l in range(n):
                if c[j]!=c[l] and r[j]>r[l]:
                    good=min(good,best[i-r[j]][l]+abs(j-l))
            best[i][j]=good
if min(best[-1])==float('inf'):
    print(-1)
else:
    print(min(best[-1]))

'''input
2 1 15
5 6
RG
'''
import math
def solve():
	n,s,k = map(int,input().split())
	s-=1
	r = list(map(int,input().split()))
	c = input()
	inf = int(1e9)
	dp = [[inf for j in range(n)] for i in range(k+1)]
	# dp[i][j] = minimum number of steps to get amount i if we start with jth index
	for i in range(0,k+1):
		for j in range(0,n):
			if i==0 or i<=r[j]:
				dp[i][j] = 0
				continue
			for K in range(0,n):
				if c[K]!=c[j] and r[K]>r[j]:
					dp[i][j] = min(dp[i][j],dp[i-r[j]][K]+int(abs(K-j)))
	ans = min(dp[k][i]+abs(i-s) for i in range(0,n))
	if ans>=inf:
		print(-1)
		return
	print(ans)
	return
t = 1
#t = int(input())
while t>0:
	t-=1
	solve()