According to the new tax scheme, a new tax called the binary string tax was introduced! JJ has a binary string S of length N. According to the tax scheme, for every occurrence of 01 in S, a tax of X rupees will be charged, while for every occurrence of 10 in S, a tax of Y rupees will be charged.

For example, if X = 5, Y = 7 and S = 11010, then S has 1 occurrence of 01 and 2 occurrences of 10, so the tax charged = 5 \cdot 1 + 7 \cdot 2 = 19 

JJ can rearrange the string S in any way he wants. He wants to minimize the amount of tax he has to pay. Can you help him do so?

------ Input Format ------ 

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains three integers N, X and Y - the length of the binary string S, the tax charged on an occurrence of 01 and the tax charged on an occurrence of 10.
- The second line of each test case contains a binary string S of length N containing 0s and 1s only.

------ Output Format ------ 

For each test case, output the minimum amount of tax that JJ has to pay.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 1000$
$1 ≤X, Y ≤100$

----- Sample Input 1 ------ 
2
4 7 3
1101
5 3 4
00000

----- Sample Output 1 ------ 
3
0

----- explanation 1 ------ 
Test Case 1: JJ can rearrange $S$ to $1110$ for which the tax charged will be $3$ which is the minimum value of tax.

Test Case 2: The tax charged for the string $S = 00000$ is $0$ which can not be reduced further.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Data structures


Solutions:
for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	s = list(input())
	if x < y:
		s.sort()
	else:
		s.sort(reverse=True)
	ans = ''
	for i in s:
		ans += i
	print(ans.count('01') * x + ans.count('10') * y)


for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	a = input()[:n]
	(s, t) = (0, 0)
	if a.count('1') == 0 or a.count('0') == 0:
		print(0)
	elif x < y:
		print(x)
	else:
		print(y)


for t in range(int(input())):
	(n, x, y) = map(int, input().split())
	s = str(input())
	one = s.count('1')
	zero = s.count('0')
	if one == 0 or zero == 0:
		print(0)
		pass
	else:
		print(y if x > y else x)
		pass
	pass


t = int(input())
for i in range(t):
	(n, x, y) = map(int, input().split())
	s = input()
	if '0' in s and '1' in s:
		if x <= y:
			print(x)
		else:
			print(y)
	else:
		print(0)


for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	tax_in = input()
	zero_one = 0
	one_zero = 0
	if '0' in tax_in and '1' in tax_in:
		if x <= y:
			print(x)
		else:
			print(y)
	else:
		print(0)


t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	s = input()
	if s.count('0') == 0 or s.count('1') == 0:
		print('0')
	elif m > k:
		print(k)
	else:
		print(m)


for i in range(int(input())):
	(n, x, y) = map(int, input().split())
	l1 = input()
	if l1.count('1') > 0 and l1.count('0') > 0:
		print(min(x, y))
	else:
		print(0)


for i in range(int(input())):
	(n, x, y) = map(int, input().split())
	str = input()
	X = 0
	Y = 0
	if x <= y:
		Xstr = sorted(str)
		xstr1 = ''.join(Xstr)
		X = xstr1.count('01')
	else:
		Ystr = sorted(str, reverse=True)
		ystr1 = ''.join(Ystr)
		Y = ystr1.count('10')
	if X == 1:
		print(x)
	elif Y == 1:
		print(y)
	else:
		print('0')


for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	s = input()
	X = 0
	Y = 0
	if x <= y:
		zeroSort = sorted(s)
		zeroStr = ''.join(zeroSort)
		X = zeroStr.count('01')
	elif x > y:
		oneSort = sorted(s, reverse=True)
		oneStr = ''.join(oneSort)
		Y = oneStr.count('10')
	if X == 1:
		print(x)
	elif Y == 1:
		print(y)
	else:
		print('0')


t = int(input())
for i in range(t):
	(n, x, y) = map(int, input().split())
	s = input()
	if s.count('10') == 0 and s.count('01') == 0:
		print('0')
	elif x <= y:
		print(x)
	else:
		print(y)


t = int(input())
for i in range(t):
	(n, b, c) = map(int, input().split())
	s = input()
	if s.count('10') == 0 and s.count('01') == 0:
		print(0)
	elif b <= c:
		print(b)
	else:
		print(c)


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	s = input()
	if s.count('01') == 0 and s.count('10') == 0:
		print(0)
	elif b <= c:
		print(b)
	else:
		print(c)


for i in range(int(input())):
	(n, x, y) = map(int, input().split())
	s = input()
	c1 = s.count('01')
	c2 = s.count('10')
	if c1 > 0 or c2 > 0:
		print(min(x, y))
	else:
		print(0)


t = int(input())
for _ in range(t):
	(n, x, y) = map(int, input().split())
	s = input()
	a = s.count('01')
	b = s.count('10')
	if a > 0 or b > 0:
		print(min(x, y))
	else:
		print(0)


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	s = input()
	c1 = s.count('10')
	c2 = s.count('01')
	if c1 > 0 or c2 > 0:
		print(min(b, c))
	else:
		print(0)


for _ in range(int(input())):
	(n, x, y) = [int(x) for x in input().split()]
	binary = input()
	if '01' in binary or '10' in binary:
		print(min(x, y))
	else:
		print('0')


for i in range(int(input())):
	(n, a, b) = [int(x) for x in input().split()]
	s = input()
	if s.count('01') > 0 or s.count('10') > 0:
		print(min(a, b))
	else:
		print(0)


for i in range(int(input())):
	(n, x, y) = map(int, input().split())
	s = input()
	if s.count('1') == n or s.count('0') == n:
		print('0')
	else:
		print(min(x, y))


t = int(input())
while t != 0:
	(n, x, y) = list(map(int, input().split()))
	s = input()
	zeros = 0
	ones = 0
	zeros = s.count('0')
	ones = s.count('1')
	if zeros == 0 or ones == 0:
		print(0)
	elif x > y:
		print(y)
	else:
		print(x)
	t -= 1


for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	s = input()
	zeros = s.count('0')
	ones = s.count('1')
	print(0 if ones == 0 or zeros == 0 else x if y > x else y)


n = int(input())
for i in range(n):
	(x, y, z) = map(int, input().split())
	a = input()
	k = 0
	t = 0
	for i in a:
		if i == '0':
			k = 1
		else:
			t = 1
	if k == 0 or t == 0:
		print(0)
	elif y < z:
		print(y)
	else:
		print(z)


t = int(input())
for _ in range(t):
	(str_len, tax_01, tax_10) = map(int, input().split())
	my_str = ''.join(sorted(input()))
	tax_total1 = 0
	for i in range(len(my_str) - 1):
		if my_str[i:i + 2] == '01':
			tax_total1 += tax_01
		elif my_str[i:i + 2] == '10':
			tax_total1 += tax_10
	my_str = my_str[::-1]
	tax_total2 = 0
	for i in range(len(my_str) - 1):
		if my_str[i:i + 2] == '01':
			tax_total2 += tax_01
		elif my_str[i:i + 2] == '10':
			tax_total2 += tax_10
	print(min(tax_total1, tax_total2))


for i in range(int(input())):
	(a, x, y) = map(int, input().split())
	l = input()
	if '0' in l and '1' in l:
		print(min(x, y))
	else:
		print(0)


t = int(input())
for i in range(t):
	(a, b, c) = map(int, input().split())
	d = list(input())
	e = d.count('0')
	f = d.count('1')
	if e == 0 or f == 0:
		print(0)
	else:
		print(min(b, c))


for t in range(int(input())):
	(a, b, c) = map(int, input().split())
	s = input()
	l = sorted(s)
	x = ''.join(l)
	y = ''.join(l[::-1])
	if b > c:
		m = y.count('01')
		n = y.count('10')
	else:
		m = x.count('01')
		n = x.count('10')
	print(b * m + c * n)


for _ in range(int(input())):
	(N, X, Y) = map(int, input().split(' '))
	s = input()
	ls = list(s)
	if X > Y:
		ls.sort()
		c = ''.join(ls[::-1])
	else:
		ls.sort()
		c = ''.join(ls)
	a = c.count('01')
	b = c.count('10')
	print(a * X + b * Y)


for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	s = input()
	l = list(s)
	if x < y:
		l.sort()
		c = ''.join(l)
	else:
		l.sort()
		c = l[::-1]
		c = ''.join(c)
	a = c.count('01')
	b = c.count('10')
	print(a * x + b * y)


t = int(input())
while t != 0:
	t = t - 1
	(n, x, y) = map(int, input().split())
	s = input()
	if '1' in s and '0' in s:
		if x < y:
			print(x * 1)
		else:
			print(y * 1)
	else:
		print(0)


t = int(input())
for i in range(t):
	(n, b, a) = map(int, input().split())
	s = input()
	m = ''
	l = ''
	for k in range(n):
		if s[k] == '1':
			m = m + '1'
		else:
			l = l + '0'
	f = m + l
	e = l + m
	if l == '' or m == '':
		print(0)
	else:
		print(min(a, b))


for i in range(int(input())):
	(n, x, y) = map(int, input().split())
	s = input()
	l = list(s)
	for i in l:
		o = l.count('1')
		z = l.count('0')
	if z == n or o == n:
		print('0')
	elif x > y:
		print(y)
	else:
		print(x)


for i in range(int(input())):
	(n, x, y) = map(int, input().split())
	s = input()
	zero = s.count('0')
	one = s.count('1')
	if zero == n or one == n:
		print(0)
	elif x > y:
		print(y)
	else:
		print(x)


for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	arr1 = [int(o) for o in list(str(input()))]
	one_count = 0
	zero_count = 0
	for p in arr1:
		if p == 1:
			one_count += 1
		else:
			zero_count += 1
	if one_count == 0 or zero_count == 0:
		print(0)
	else:
		print(min(x, y))


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	d = set(input())
	if len(d) == 1:
		print(0)
	elif b >= c:
		print(c)
	else:
		print(b)


def test():
	(n, x, y) = map(int, input().split())
	s = input()
	ones = s.count('1')
	zero = s.count('0')
	if ones == 0 or zero == 0:
		print(0)
		return
	if x > y:
		print(y)
	else:
		print(x)
t = int(input())
for _ in range(t):
	test()


for i in range(int(input())):
	(N, X, Y) = map(int, input().split())
	S = input()
	if '0' in S and '1' in S:
		print(min(X, Y))
	else:
		print(0)


for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	s = str(input())
	if '1' not in s or '0' not in s:
		print('0')
	elif x > y:
		print(y)
	else:
		print(x)


for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	s = list(input())
	if x < y:
		s.sort()
	else:
		s.sort(reverse=True)
	s = ''.join(s)
	t1 = s.count('01')
	t2 = s.count('10')
	print(x * t1 + y * t2)


t = int(input())
for i in range(t):
	(n, x, y) = map(int, input().split())
	s = input()
	if '1' not in s or '0' not in s:
		print('0')
	elif x > y:
		print(y)
	else:
		print(x)


for i in range(int(input())):
	(N, K, L) = map(int, input().split())
	A = input()
	mins = min(K, L)
	print(0 if A.count('1') == 0 or A.count('0') == 0 else mins)


for i in range(int(input())):
	(n, x, y) = [int(i) for i in input().split()]
	z = input()
	k = z.count('1')
	j = z.count('0')
	if k == n or j == n:
		print(0)
	elif x > y:
		print(y)
	else:
		print(x)


x = int(input())
for i in range(x):
	(a, b, c) = map(int, input().split())
	s = input()
	k = s.count('0')
	l = s.count('1')
	if k == 0 or l == 0:
		print(0)
	elif b > c:
		print(c)
	else:
		print(b)


t = int(input())
while t > 0:
	(n, x, y) = map(int, input().split())
	s = list(input())
	s.sort(reverse=True)
	if '1' in s and '0' in s:
		if x < y:
			print(x)
		else:
			print(y)
	else:
		print(0)
	t = t - 1


for _ in range(int(input())):
	(number, x, y) = map(int, input().split())
	s = input()
	if s.count('0') == number or s.count('1') == number:
		print('0')
	elif x > y:
		print(y)
	else:
		print(x)


for _ in range(int(input())):
	(s, x, y) = map(int, input().split())
	a = input()
	if a.count('0') == s or a.count('1') == s:
		print(0)
	else:
		print(min(x, y))


t = int(input())
for i in range(t):
	(n, x, y) = map(int, input().split())
	s = input()
	c = 0
	d = 0
	for i in range(len(s)):
		if s[i] == '0':
			c += 1
		else:
			d += 1
	if c == len(s) or d == len(s):
		print('0')
	else:
		print(min(x, y))


for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	s = input()
	if '1' in s and '0' in s:
		print(min(x, y))
	else:
		print(0)


for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	s1 = input()
	if s1.count('0') == n or s1.count('1') == n:
		print(0)
	else:
		print(min(x, y))


for _ in range(int(input())):
	(n, x, y) = map(int, input().split())
	s1 = input()
	s2 = list(map(int, s1))
	s3 = s2.count(0)
	s4 = s2.count(1)
	if s3 == n or s4 == n:
		print('0')
	else:
		print(min(x, y))


t = int(input())
for i in range(t):
	(n, x, y) = map(int, input().split())
	s = input()
	s = list(map(int, s))
	s1 = s.count(0)
	s2 = s.count(1)
	if s1 == n or s2 == n:
		print(0)
	elif x > y:
		print(y)
	else:
		print(x)


t = int(input())
for i in range(t):
	(n, x, y) = map(int, input().split())
	s = input()
	zc = 0
	oc = 0
	for k in s:
		if k == '1':
			oc = oc + 1
		else:
			zc = zc + 1
	if oc == 0 or zc == 0:
		print(0)
	else:
		print(min(x, y))