You're creating a game level for some mobile game. The level should contain some number of cells aligned in a row from left to right and numbered with consecutive integers starting from $1$, and in each cell you can either put a platform or leave it empty.

In order to pass a level, a player must throw a ball from the left so that it first lands on a platform in the cell $p$, then bounces off it, then bounces off a platform in the cell $(p + k)$, then a platform in the cell $(p + 2k)$, and so on every $k$-th platform until it goes farther than the last cell. If any of these cells has no platform, you can't pass the level with these $p$ and $k$.

You already have some level pattern $a_1$, $a_2$, $a_3$, ..., $a_n$, where $a_i = 0$ means there is no platform in the cell $i$, and $a_i = 1$ means there is one. You want to modify it so that the level can be passed with given $p$ and $k$. In $x$ seconds you can add a platform in some empty cell. In $y$ seconds you can remove the first cell completely, reducing the number of cells by one, and renumerating the other cells keeping their order. You can't do any other operation. You can not reduce the number of cells to less than $p$.

Illustration for the third example test case. Crosses mark deleted cells. Blue platform is the newly added.

What is the minimum number of seconds you need to make this level passable with given $p$ and $k$?


-----Input-----

The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of test cases follows.

The first line of each test case contains three integers $n$, $p$, and $k$ ($1 \le p \le n \le 10^5$, $1 \le k \le n$) — the number of cells you have, the first cell that should contain a platform, and the period of ball bouncing required.

The second line of each test case contains a string $a_1 a_2 a_3 \ldots a_n$ ($a_i = 0$ or $a_i = 1$) — the initial pattern written without spaces.

The last line of each test case contains two integers $x$ and $y$ ($1 \le x, y \le 10^4$) — the time required to add a platform and to remove the first cell correspondingly.

The sum of $n$ over test cases does not exceed $10^5$.


-----Output-----

For each test case output a single integer — the minimum number of seconds you need to modify the level accordingly.

It can be shown that it is always possible to make the level passable.


-----Examples-----

Input
3
10 3 2
0101010101
2 2
5 4 1
00000
2 10
11 2 3
10110011000
4 3
Output
2
4
10


-----Note-----

In the first test case it's best to just remove the first cell, after that all required platforms are in their places: 0101010101. The stroked out digit is removed, the bold ones are where platforms should be located. The time required is $y = 2$.

In the second test case it's best to add a platform to both cells $4$ and $5$: 00000 $\to$ 00011. The time required is $x \cdot 2 = 4$.

In the third test case it's best to to remove the first cell twice and then add a platform to the cell which was initially $10$-th: 10110011000 $\to$ 10110011010. The time required is $y \cdot 2 + x = 10$.

Difficulty: MEDIUM
Tags: Dynamic programming

Implementation

Complete search
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
def solve():
	(n, p, k) = map(int, input().split())
	blocks = input()
	(x, y) = map(int, input().split())
	costs = [0] * n
	for i in range(n - 1, p - 2, -1):
		if i + k < n:
			costs[i] = costs[i + k]
		if blocks[i] == '0':
			costs[i] += x
	for i in range(p - 1, n):
		costs[i] += y * (i - p + 1)
	print(min(costs[p - 1:]))

def main():
	for _ in range(int(input())):
		solve()
main()


for _ in range(int(input())):
	(n, p, k) = map(int, input().strip().split())
	s = input()
	(x, y) = map(int, input().strip().split())
	l = [0] * n
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			l[i] += x
		if i < n - k:
			l[i] += l[i + k]
	for i in range(0, n - p + 1):
		l[i + p - 1] += i * y
	print(min(l[p - 1:]))


def fill(A, k, dp, x):
	for i in range(1, k + 1):
		j = len(A) - i
		addcost = 0
		while j >= 0:
			addcost += (A[j] == '0') * x
			dp[j] = addcost
			j = j - k

def fun(A, x, y, k, p, dp):
	rcost = 0
	s = 0
	mini = dp[p - 1]
	i = p - 1 + s
	while rcost < mini and p + s <= len(A):
		i = p - 1 + s
		addcost = dp[i]
		totalcost = addcost + rcost
		mini = min(mini, totalcost)
		rcost += y
		s += 1
	return mini
for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	A = input()
	(x, y) = map(int, input().split())
	dp = [0 for i in range(len(A) + 1)]
	fill(A, k, dp, x)
	print(fun(A, x, y, k, p, dp))


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	blocks = input()
	(x, y) = map(int, input().split())
	costs = [0] * n
	for i in range(n - 1, p - 2, -1):
		if i + k < n:
			costs[i] = costs[i + k]
		if blocks[i] == '0':
			costs[i] += x
	for i in range(p - 1, n):
		costs[i] += y * (i - p + 1)
	print(min(costs[p - 1:]))


t = int(input())
for i in range(t):
	(n, p, k) = map(int, input().split())
	l = list(input())
	(x, y) = map(int, input().split())
	val = [0] * n
	ans = x * n + y * n
	for j in range(n - 1, -1, -1):
		if l[j] == '0':
			val[j] = x + val[j + k] if j + k < n else x
		else:
			val[j] = val[j + k] if j + k < n else 0
	for j in range(p - 1, n, 1):
		ans = min(ans, (j + 1 - p) * y + val[j])
	print(ans)


for i in range(int(input())):
	(n, p, k) = map(int, input().split())
	l = [*input()]
	(x, y) = map(int, input().split())
	q = [0 for i in range(n)]
	r = []
	for i in range(n - 1, n - k - 1, -1):
		w = 0
		for j in range(i, -1, -k):
			if l[j] == '0':
				w += x
			q[j] += w
	for i in range(p - 1, n):
		r += [y * (i - p + 1) + q[i]]
	print(min(r))


import sys
from collections import Counter

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))
sys.setrecursionlimit(20000)
T = int(input())
for _ in range(T):
	(n, p, k) = get_ints()
	A = list(map(int, sys.stdin.readline().strip()))
	(x, y) = get_ints()
	C = [0] * n
	for i in range(n):
		if i < k:
			C[n - 1 - i] = 1 - A[n - 1 - i]
		else:
			C[n - 1 - i] = C[n - 1 - i + k] + (1 - A[n - 1 - i])
	min_time = float('inf')
	for i in range(p - 1, n):
		current_time = C[i] * x + (i - (p - 1)) * y
		if current_time < min_time:
			min_time = current_time
	print(min_time)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = input()
	(x, y) = map(int, input().split())
	p -= 1
	n -= p
	a = a[p:]
	ans = [0] * n
	for i in range(n - 1, -1, -1):
		ans[i] = ans[i + k] - y * k if i + k < n else i * y
		if a[i] == '0':
			ans[i] += x
	print(min(ans))


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	arr = [int(x) for x in input()]
	(x, y) = map(int, input().split())
	ans = float('inf')
	l = 1
	for i in range(p - 1, p + k - 1):
		cnt = 0
		for j in range(n - l, p - 2, k * -1):
			if arr[j] == 0:
				cnt += 1
			ans = min(abs(j + 1 - p) * y + cnt * x, ans)
		l += 1
	print(ans)


def solve():
	(cells, first_cell, period) = map(int, input().split())
	first_cell -= 1
	pattern = list(map(int, input()))
	(add_platform, reduce_cell) = map(int, input().split())
	dp = [0] * cells
	for i in range(cells - 1, -1, -1):
		dp[i] = 1 - pattern[i]
		if i + period < cells:
			dp[i] += dp[i + period]
	lambdafun = lambda t: reduce_cell * (t - first_cell) + add_platform * dp[t]
	return min(map(lambdafun, range(first_cell, cells)))
for _ in range(int(input())):
	print(solve())


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	s = input()
	(x, y) = map(int, input().split())
	mem = [0] * (n + 1)
	for i in range(n - 1, p - 2, -1):
		if s[i] == '0':
			if i + k < n:
				mem[i] = mem[i + k]
			mem[i] += 1
		elif i + k < n:
			mem[i] = mem[i + k]
	ans = n * (x + y)
	for i in range(p - 1, n):
		ans = min(ans, x * mem[i] + y * (i - (p - 1)))
	print(ans)


import sys

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

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	(n, p, k) = mints()
	a = list(map(int, minp()))
	(x, y) = mints()
	dp = [0] * n
	for i in range(n - 1, max(n - k - 1, -1), -1):
		dp[i] = int(a[i] == 0)
	for i in range(n - k - 1, -1, -1):
		dp[i] = int(a[i] == 0) + dp[i + k]
	ans = int(9e+18)
	for i in range(p - 1, n):
		ans = min(ans, dp[i] * x + (i - (p - 1)) * y)
	print(ans)
for i in range(mint()):
	solve()


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	t = int(input())
	for _ in range(t):
		(n, p, k) = map(int, input().split())
		p -= 1
		A = input().rstrip()
		(x, y) = map(int, input().split())
		dp = [f_inf] * n
		if A[p] == '0':
			dp[p] = x
		else:
			dp[p] = 0
		j = 1
		for i in range(p + 1, n):
			dp[i] = j * y
			if A[i] == '0':
				dp[i] += x
			j += 1
		res = f_inf
		for i in range(p, n):
			if i + k >= n:
				res = min(res, dp[i])
				continue
			if A[i + k] == '0':
				dp[i + k] = min(dp[i + k], dp[i] + x)
			else:
				dp[i + k] = min(dp[i + k], dp[i])
		print(res)
resolve()


import math

def solve(n, p, k, A, x, y):
	creates = [0 for _ in range(n + 1)]
	cases = min(k, n - p + 1)
	for i in range(cases):
		start = n - i
		while start >= p:
			if A[start - 1] == '0':
				creates[start] += 1
			if start + k <= n:
				creates[start] += creates[start + k]
			start -= k
	cost = [0 for _ in range(n + 1)]
	for i in range(p, n + 1):
		cost[i] = x * creates[i] + (i - p) * y
	return min(cost[p:])
t = int(input())
for i in range(t):
	(n, p, k) = map(int, input().split())
	A = input()
	(x, y) = map(int, input().split())
	print(str(solve(n, p, k, A, x, y)))


for tt in range(int(input())):
	(n, p, k) = map(int, input().split())
	s = 'x' + input()
	(x, y) = map(int, input().split())
	ma = 10 ** 9
	dp = [ma for i in range(n + 1)]
	cnt = 0
	for i in range(p, p + k):
		if i > n:
			break
		dp[i] = cnt * y
		if s[i] == '0':
			dp[i] += x
		cnt += 1
	for i in range(p + k, n + 1):
		dp[i] = min((i - p) * y, dp[i - k])
		if s[i] == '0':
			dp[i] += x
	ans = 10 ** 9
	for i in range(n - k + 1, n + 1):
		ans = min(ans, dp[i])
	print(ans)


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	plat = '0' + input()
	(x, y) = map(int, input().split())
	cost = [0] * (n + 1)
	for i in range(n, p - 1, -1):
		if i + k <= n:
			cost[i] = cost[i + k]
		if plat[i] == '0':
			cost[i] += x
	for i in range(p, n + 1):
		cost[i] += y * (i - p)
	print(min(cost[p:]))


cases = int(input())
while cases > 0:
	(n, p, k) = map(int, input().split())
	a = [int(d) for d in str(input())]
	(x, y) = map(int, input().split())
	time = float('inf')
	l = 1
	for i in range(p - 1, p + k - 1):
		count = 0
		for j in range(n - l, p - 2, k * -1):
			if a[j] == 0:
				count += 1
			time = min(abs(j + 1 - p) * y + count * x, time)
		l += 1
	cases -= 1
	print(time)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	s = input()
	(x, y) = map(int, input().split())
	dp = [0] * n
	for i in range(n - 1, -1, -1):
		if i + k < n:
			dp[i] += dp[i + k] + (s[i] == '0')
		else:
			dp[i] += s[i] == '0'
	ans = 2e+18
	for i in range(n):
		if i >= p - 1:
			ans = min((i - p + 1) * y + dp[i] * x, ans)
	print(ans)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = list(input())
	(x, y) = map(int, input().split())
	minn = float('inf')
	l = 1
	for i in range(p - 1, p + k - 1):
		cnt = 0
		for j in range(n - l, p - 2, k * -1):
			if a[j] == '0':
				cnt += 1
			minn = min(minn, abs(j + 1 - p) * y + cnt * x)
		l += 1
	print(minn)


from collections import defaultdict
for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	s = input()
	(x, y) = map(int, input().split())
	dp = [0] * n
	for i in range(n - 1, -1, -1):
		if i + k >= n and s[i] == '0':
			dp[i] = x
		elif i + k < n:
			if s[i] == '0':
				dp[i] = x + dp[i + k]
			else:
				dp[i] = dp[i + k]
	mini = dp[p - 1]
	for r in range(n - p + 1):
		cost = r * y
		i = r + p - 1
		if i >= n:
			mini = min(cost, mini)
			break
		else:
			mini = min(cost + dp[i], mini)
	print(mini)


t = int(input())
for i in range(t):
	(n, p, k) = [int(i) for i in input().split()]
	a = str(input())
	(x, y) = [int(i) for i in input().split()]
	c = [0] * n
	res = 1000000000000
	for j in range(n - 1, -1, -1):
		if n - j - 1 < k:
			c[j] = 1 - int(a[j])
		else:
			c[j] = c[j + k] + 1 - int(a[j])
	for j in range(p - 1, n, 1):
		c[j] = x * c[j] + y * (j - p + 1)
		res = min(res, c[j])
	print(res)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	s = input()
	l = list(s)
	(x, y) = map(int, input().split())
	dpk = [0] * n
	for i in range(n - k, n):
		if l[i] == '0':
			dpk[i] = x
	for i in range(n - k - 1, -1, -1):
		if l[i] == '1':
			dpk[i] += dpk[i + k]
		else:
			dpk[i] += x + dpk[i + k]
	ans = float('inf')
	for i in range(p - 1, n):
		dpk[i] += y * (i - p + 1)
		ans = min(ans, dpk[i])
	print(ans)


t = int(input())
for i in range(t):
	(n, p, k) = map(int, input().split())
	s = input()
	(x, y) = map(int, input().split())
	ans1 = 0
	c = [0] * n
	for l in range(k):
		c[n - l - 1] = 1 - int(s[n - l - 1])
	for l in range(n - k - 1, p - 2, -1):
		c[l] = c[l + k] + 1 - int(s[l])
	min1 = 10000000000000
	sum = 0
	for q in range(p - 1, n):
		sum = c[q] * x + (q - p + 1) * y
		if sum < min1:
			min1 = sum
	print(min1)


t = int(input())
for i in range(t):
	(n, p, k) = map(int, input().split())
	s = input()
	(x, y) = map(int, input().split())
	summ = 0
	arr = [0] * n
	for j in range(k):
		arr[n - j - 1] = 1 - int(s[n - j - 1])
	for j in range(n - k - 1, p - 2, -1):
		arr[j] = arr[j + k] + 1 - int(s[j])
	mini = 1000000000
	for j in range(p - 1, n):
		val = x * arr[j] + y * (j - p + 1)
		if val < mini:
			mini = val
	print(mini)


t = int(input())
for i in range(0, t):
	l1 = [int(x) for x in input().split()]
	n = l1[0]
	p = l1[1]
	k = l1[2]
	inp_str = input()
	l2 = [int(x) for x in input().split()]
	add = l2[0]
	rem = l2[1]
	c = [0 for x in range(0, n)]
	for j in range(n - 1, -1, -1):
		if j + k < n:
			if inp_str[j] == '0':
				c[j] = c[j + k] + 1
			else:
				c[j] = c[j + k]
		elif inp_str[j] == '0':
			c[j] = 1
		else:
			c[j] = 0
	p -= 1
	mini = 10 ** 9
	for j in range(p, n):
		val = (j - p) * rem + add * c[j]
		if mini > val:
			mini = val
	print(mini)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	a = input()
	(x, y) = map(int, input().split())
	r = 999999999
	s = [0] * k
	for q in range(k):
		count = 0
		for i in range(q, n, k):
			if i >= p - 1 and a[i] == '0':
				count += 1
		s[q] = count
	for i in range(p - 1, n):
		r = min(x * s[i % k] + y * (i - p + 1), r)
		s[i % k] -= 0 if a[i] == '1' else 1
	print(r)


t = int(input())
for z in range(t):
	(n, p, k) = map(int, input().split())
	a = input()
	(x, y) = map(int, input().split())
	result = 10 ** 18
	dp = [10 ** 18] * n
	for i in range(n):
		if i + 1 < p:
			continue
		if i + 1 < k:
			if a[i] == '0':
				dp[i] = y * (i - p + 1) + x
			else:
				dp[i] = y * (i - p + 1)
		elif a[i] == '0':
			dp[i] = min(dp[i - k], y * (i - p + 1)) + x
		else:
			dp[i] = min(dp[i - k], y * (i - p + 1))
		if n - i - 1 < k:
			result = min(result, dp[i])
	print(result)


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	a = list(str(input()))
	(x, y) = map(int, input().split())
	cost = [0 for i in range(k)]
	for i in range(p - 1, n):
		a[i] = int(a[i])
		if a[i] == 0:
			cost[i % k] += x
			a[i] = 2
	mn = 10 ** 12
	for i in range(p - 1, n):
		mn = min(mn, cost[i % k] + y * (i - p + 1))
		if a[i] == 2:
			cost[i % k] -= x
	print(mn)


for z in range(int(input())):
	(n, p, k) = map(int, input().split())
	p -= 1
	a = input()
	b = [0] * n
	(x, y) = map(int, input().split())
	ss = n - p
	for i in range(p, n):
		b[i] = (i - p) * y + (x if a[i] == '0' else 0)
	for i in range(p + k, n):
		if a[i] == '0':
			b[i] = min(b[i], b[i - k] + x)
		else:
			b[i] = min(b[i], b[i - k])
	c = 99999999999999
	for i in range(-1, -min(k, ss) - 1, -1):
		if b[i] < c:
			c = b[i]
	print(c)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	s = ' ' + input()
	(x, y) = map(int, input().split())
	f = [0] * (n + 3)
	kq = 10 ** 12
	for i in range(1, n + 1):
		if i < p:
			f[i] = 10 ** 12
			continue
		f[i] = y * (i - p)
		if i - k > 0:
			f[i] = min(f[i], f[i - k])
		if s[i] == '0':
			f[i] += x
		if i + k > n:
			kq = min(f[i], kq)
	print(kq)


from sys import stdin
from collections import deque
T = int(stdin.readline().strip())
for casos in range(T):
	(n, p, k) = map(int, stdin.readline().strip().split())
	s = stdin.readline().strip()
	(x, y) = map(int, stdin.readline().strip().split())
	cnt = deque([0 for i in range(k)])
	x1 = 0
	ans = 10 ** 50
	c = 0
	for i in range(n - 1, p - 2, -1):
		if s[i] == '1':
			ans = min(ans, (i - p + 1) * y + (x1 // k - cnt[0]) * x)
			cnt[0] += 1
		else:
			ans = min(ans, x + (i - p + 1) * y + (x1 // k - cnt[0]) * x)
		x1 += 1
		cnt.appendleft(cnt[-1])
		cnt.pop()
	print(ans)


t = int(input())
for q in range(t):
	(n, p, k) = map(int, input().split())
	a = list(map(int, input()))
	(x, y) = map(int, input().split())
	dp = [-1] * (n + 1)
	for i in range(p, n + 1):
		dp[i] = y * (i - p) + (a[i - 1] + 1) % 2 * x
	for i in range(p + k, n + 1):
		dp[i] = min(dp[i], dp[i - k] + (a[i - 1] + 1) % 2 * x)
	md = 10000000000000000
	for i in range(1, k + 1):
		if dp[-i] != -1 and dp[-i] < md:
			md = dp[-i]
	print(md)


t = int(input())
for _ in range(t):
	(n, p, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input()]
	(x, y) = [int(i) for i in input().split()]
	b = [0 for i in range(n)]
	for i in range(n - k, n):
		b[i] = 1 - a[i]
	for i in range(n - k - 1, -1, -1):
		b[i] = b[i + k] + 1 - a[i]
	tmin = x * n
	for i in range(p - 1, n):
		t = (i - p + 1) * y + b[i] * x
		tmin = min(tmin, t)
	print(tmin)


t = int(input())
for t in range(0, t):
	q = list(map(int, input().rstrip().split()))
	n = q[0]
	p = q[1]
	k = q[2]
	st = input()
	r = list(map(int, input().rstrip().split()))
	x = r[0]
	y = r[1]
	count = []
	j = p
	while j <= n and j < p + k:
		co = 0
		for d in range(j, n + 1, k):
			if st[d - 1] == '0':
				co = co + 1
		count.append(co)
		j = j + 1
	v = 0
	ca = []
	for i in range(p + k, n + 1):
		if st[i - k - 1] == '0':
			count.append(count[v] - 1)
		else:
			count.append(count[v])
		v = v + 1
	i = 0
	for e in count:
		cost = i * y + e * x
		ca.append(cost)
		i = i + 1
	ca.sort()
	print(ca[0])


for _ in range(int(input())):
	(n, p, k) = [*map(int, input().split())]
	l = [1 - int(i) for i in input()]
	(x, y) = [*map(int, input().split())]
	dp = [float('inf') for i in range(n)]
	for i in range(n):
		if i < p - 1:
			continue
		dp[i] = min((i - p + 1) * y + l[i] * x, dp[i - k] + l[i] * x if i - k >= 0 else float('inf'))
	print(min(dp[n - k:]))


from collections import Counter
from collections import OrderedDict
from collections import defaultdict
import bisect
import math
from sys import setrecursionlimit

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def fre_count(mylist):
	return Counter(mylist)
t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	arr = [int(x) for x in input()]
	(x, y) = map(int, input().split())
	ans = float('inf')
	l = 1
	for i in range(p - 1, p + k - 1):
		cnt = 0
		for j in range(n - l, p - 2, k * -1):
			if arr[j] == 0:
				cnt += 1
			ans = min(abs(j + 1 - p) * y + cnt * x, ans)
		l += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	s = input()
	(x, y) = map(int, input().split())
	add_cost = [0 for i in range(n - p + 1)]
	for i in range(n - p, -1, -1):
		add_cost[i] = 1 - int(s[i + p - 1])
		if i + k <= n - p:
			add_cost[i] += add_cost[i + k]
	ans = add_cost[0] * x
	for i in range(1, n - p + 1):
		curr_cost = add_cost[i] * x + i * y
		ans = min(ans, curr_cost)
	print(ans)


for y in range(int(input())):
	(a, b, c) = map(int, input().split())
	s = input()
	(x, y) = map(int, input().split())
	ans = [0] * c
	t = 0
	for i in range(b - 1, a):
		if t >= c:
			t = 0
		if s[i] == '0':
			ans[t] += 1
		t += 1
	t = 0
	by = 0
	minn = 1000000001
	for i in range(b - 1, a):
		if t >= c:
			t = 0
		cnt = ans[t] * x
		if ans[t] > 0 and s[i] == '0':
			ans[t] -= 1
		minn = min(minn, cnt + by)
		by += y
		t += 1
	print(minn)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, p, k) = [*map(int, input().split())]
	l = [1 - int(i) for i in input().strip()]
	(x, y) = [*map(int, input().split())]
	dp = [float('inf') for i in range(n)]
	for i in range(n):
		if i < p - 1:
			continue
		dp[i] = min((i - p + 1) * y + l[i] * x, dp[i - k] + l[i] * x if i - k >= 0 else float('inf'))
	print(min(dp[n - k:]))


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	s = input()
	(x, y) = map(int, input().split())
	dp = [0] * n
	for i in range(k):
		if s[n - i - 1] == '1':
			dp[i] = 0
		else:
			dp[i] = x
	for i in range(k, n - p + 1):
		if s[n - i - 1] == '1':
			dp[i] = 0
		else:
			dp[i] = x
		dp[i] += dp[i - k]
	dp = dp[::-1]
	ans = 99999999999999999
	i = 0
	dop = 0
	while n - i + 1 > p:
		ans = min(ans, dp[i + p - 1] + dop)
		i += 1
		dop += y
	print(ans)


tc = int(input())
while tc:
	(n, p, k) = map(int, input().split())
	st = '#' + input()
	(x, y) = map(int, input().split())
	ans = -1
	dp = [0] * (n + 1)
	for i in reversed(range(1, n + 1)):
		if i + k > n:
			if st[i] == '0':
				dp[i] = 1
		else:
			if st[i] == '0':
				dp[i] = 1
			dp[i] += dp[i + k]
	for j in range(p, n + 1):
		a = (j - p) * y + dp[j] * x
		if ans == -1 or a < ans:
			ans = a
	print(ans)
	tc -= 1


t = int(input())
for j in range(t):
	(n, p, k) = map(int, input().split())
	s = input()
	s = '~' + s
	(x, y) = map(int, input().split())
	a = [0] * n
	b = [0] * n
	ans = 9999999999
	for i in range(p, n + 1):
		a[(i - p) % k] += s[i] == '0'
	for i in range(p, n + 1):
		ans = min(ans, (i - p) * y + (a[(i - p) % k] - b[(i - p) % k]) * x)
		b[(i - p) % k] += s[i] == '0'
	print(ans)


try:
	inp = open('file.txt').readline
except:
	inp = input
t = int(inp().strip())
for _ in range(t):
	(n, p, k) = map(int, inp().strip().split(' '))
	arr = list(inp().strip())
	(y, x) = map(int, inp().strip().split(' '))
	kcou = [0 for i in range(n)]
	i = 0
	for i in range(n - 1, n - k - 1, -1):
		j = i
		while j >= 0:
			if arr[j] != '1':
				kcou[j] += 1
			if j + k < n:
				kcou[j] += kcou[j + k]
			j -= k
	ans = int(1000000000.0)
	rem = 0
	for i in range(p - 1, n):
		if arr[i] == '1':
			cur = rem * x
			if i + k < n:
				cur += kcou[i + k] * y
			ans = min(ans, cur)
		else:
			cur = rem * x + y
			if i + k < n:
				cur += kcou[i + k] * y
			ans = min(ans, cur)
		rem += 1
	print(ans)


a = int(input())
for i in range(0, a):
	(n, p, k) = map(int, input().split())
	p = p - 1
	s = input()
	(x, y) = map(int, input().split())
	arr = [int(i) for i in s]
	d = dict()
	for i in range(p, len(arr)):
		if (i - p) % k in d:
			d[(i - p) % k].append(arr[i])
		else:
			d[(i - p) % k] = [arr[i]]
	mic = dict()
	for i in d:
		incost = d[i].count(0)
		mic[i] = i * y + incost * x
		for j in range(1, len(d[i])):
			if d[i][j - 1] == 0:
				incost = incost - 1
			thiscost = incost * x + j * y * k + i * y
			mic[i] = min(mic[i], thiscost)
	minn = float('inf')
	for i in mic:
		minn = min(mic[i], minn)
	print(minn)


t = int(input())
for l in range(t):
	(n, p, k) = map(int, input().split())
	a = list(map(int, list(input())))
	a = [1 - a[i] for i in range(n)]
	(x, y) = map(int, input().split())
	p -= 1
	mn = n * x
	sumadds = [0] * k
	start = [i for i in range(k)]
	for i in range(n):
		sumadds[i % k] += a[i]
	for i in range(p, n):
		while start[i % k] != i:
			sumadds[i % k] -= a[start[i % k]]
			start[i % k] += k
		mn = min(mn, sumadds[i % k] * x + (i - p) * y)
	print(mn)