Given the schedule of Chef for 30 days (A binary string of length 30 where '0' denotes that Chef was on leave and '1' denotes Chef was working on that day). Chef gets X- Rs for every day he worked. As working continuously for a long time is hectic so Company introduced the following policy to give a bonus to its employees.

The company will check the longest streak for which an employee has worked and will award Y- Rs for every day of that streak as a bonus. Calculate the salary received by Chef (including the bonus).

Note: Rs represents the currency of Chefland, and if there are two or more longest streaks of the same length, only one is counted for the bonus.

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

- The first line contains an integer T denoting the number of test cases. The T test cases then follow.
- The first line of each test case contains X and Y.
- Second line contains a binary string (i.e it contains only ‘0’ / ‘1’), where '0' denotes that Chef was on leave and '1' denotes Chef was working on that day.

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

- For each testcase, output in a single line answer to the problem. i.e The salary received by Chef (including the bonus).

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ X ≤ 999$
$1 ≤ Y ≤ 999$
$|S| = 30$

----- Sample Input 1 ------ 
3
6 3
111100110101100000101100011111
8 2
111010111101001010100100111101
5 6
011101010100101000001101000010
----- Sample Output 1 ------ 
117
152
78
----- explanation 1 ------ 
Testcase $1$: Chef's actual pay comes out $17 \cdot 6 = 102-$ Rs and the length of longest continuous working streak comes out $5$ (the last $5$ working days), so bonus reward becomes $5 \cdot 3 = 15-$ Rs. Hence Chef's salary comes out to be $102 + 15 = 117-$ Rs. 

Testcase $2$: Chef's actual pay comes out $144-$ Rs and the length of longest continuous working streak comes out $4$ (here there are multiple occurrences of the longest working streak, so company selects any one of them), so bonus reward becomes $8-$ Rs. Hence Chef's salary comes out to be $152-$ Rs.

Source: codechef | Difficulty: EASY
Tags: Data structures

Mathematics

Complete search


Solutions:
t = int(input())
while t:
	arr = list(map(int, input().split()))
	x = arr[0]
	y = arr[1]
	ip = input()
	count1 = 0
	count2 = 0
	temp = 0
	for i in ip:
		if i == '1':
			count1 += 1
			temp += 1
			count2 = max(temp, count2)
		else:
			temp = 0
	print(x * count1 + y * count2)
	t -= 1


t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	s = input()
	working = s.count('1') * x
	count = 0
	l = []
	for i in s:
		if i == '1':
			count += 1
		else:
			l.append(count)
			count = 0
	else:
		l.append(count)
	streak = max(l) * y
	print(working + streak)


for _ in range(int(input())):
	(X, Y) = input().split()
	string = input()
	X = int(X)
	Y = int(Y)
	count = 0
	max_cooccurence = 0
	prev = 0
	for i in range(len(string)):
		if string[i] == '1':
			count += 1
			max_cooccurence += 1
		else:
			max_cooccurence = 0
		if max_cooccurence > prev:
			prev = max_cooccurence
	sum = count * X + prev * Y
	print(sum)


for _ in range(int(input())):
	(x, y) = map(int, input().strip().split())
	s = input()
	cont = 0
	total = 0
	temp = 0
	for i in s:
		if i == '1':
			total += 1
			temp += 1
			cont = max(cont, temp)
		else:
			temp = 0
	print(total * x + cont * y)


t = int(input())
while t != 0:
	list1 = []
	count = 0
	cost = 0
	(x, y) = [int(x) for x in input().split()]
	m = input()
	lum = m.count('1')
	cost = cost + lum * x
	i = 0
	while i < len(m):
		if i == len(m) - 1 and m[i] == '1':
			count = count + 1
			list1.append(count)
		elif m[i] == '1':
			count = count + 1
		else:
			list1.append(count)
			count = 0
			a = m[i]
		i = i + 1
	z = max(list1)
	cost = cost + z * y
	print(cost)
	t = t - 1


for i in range(int(input())):
	(x, y) = map(int, input().split())
	s = input()
	one = s.count('1')
	l1 = s.split('0')
	m = -1
	for i in range(len(l1)):
		if len(l1[i]) > m:
			m = len(l1[i])
	print(one * x + m * y)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	s = input()
	s = str(s)
	c1 = s.count('1')
	x = c1 * a
	l = []
	l1 = s.split('0')
	m = -1
	for i in range(len(l1)):
		if len(l1[i]) > m:
			m = len(l1[i])
	y = m * b
	print(x + y)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	s = str(input())
	a = s.count('1') * x
	l = []
	l1 = s.split('0')
	max = -1
	for i in range(len(l1)):
		if len(l1[i]) > max:
			max = len(l1[i])
	b = max * y
	print(a + b)


T = int(input())
for i in range(T):
	(X, Y) = map(int, input().split())
	S = list(map(int, input()))
	c = 0
	for j in S:
		if j == 1:
			c += 1
	B = 0
	for k in range(len(S)):
		P = 0
		for n in range(k, len(S)):
			if S[n] == 1:
				P += 1
			else:
				break
		if P > B:
			B = P
	P1 = X * c
	P2 = Y * B
	print(P1 + P2)


for _ in range(int(input())):
	(x, y) = map(int, input().split(' '))
	a = input()
	print(a.count('1') * x + len(max(set(a.split('0')) - {''})) * y)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	s = input()
	l = sorted(set(map(str, s.split('0'))))
	print(s.count('1') * x + l[-1].count('1') * y)


t = int(input())
for tc in range(t):
	(x, y) = map(int, input().split())
	s = input()
	a = s.count('1')
	c = 0
	d = []
	for j in s:
		if j == '1':
			c += 1
		else:
			d.append(c)
			c = 0
	d.append(c)
	b = a * x
	v = max(d) * y
	print(b + v)


import re
n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	s = input()
	o = s.count('1')
	res = len(max(re.findall('1' + '+', s), key=len))
	print(o * x + res * y)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	b = input()
	c = b.count('1')
	s = 0
	streak = []
	for i in b:
		if i == '1':
			s += 1
		else:
			streak.append(s)
			s = 0
	streak.append(s)
	print(c * x + max(streak) * y)


t = int(input())
l = []
for nn in range(0, t):
	hkl = str(input())
	pp = hkl.split(' ')
	vv = []
	for nbc in pp:
		vv.append(int(nbc))
	njt = str(input())
	vv.append(njt)
	l.append(vv)
for nxza in l:
	sal = 0
	b = 0
	bft = 0
	o = 0
	i = 0
	for xxs in range(0, len(nxza[-1])):
		if nxza[-1][xxs] == '1':
			sal += nxza[0]
			i = 1
			o += 1
		if nxza[-1][xxs] == '0':
			if o > bft:
				bft = o
			o = 0
			i = 0
		if xxs == len(nxza[-1]) - 1:
			if o > bft:
				bft = o
	b = bft * nxza[1]
	ans = sal + b
	print(ans)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	s = input()
	a = x * s.count('1')
	b = 1
	l = []
	for i in range(len(s) - 1):
		if s[i] == '1' and s[i + 1] == '1':
			b += 1
		else:
			l.append(b)
			b = 1
	l.append(b)
	c = max(l) * y
	print(a + c)


import math
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	s = input()
	p = s.count('1')
	s = s.split('0')
	s.sort()
	a = len(max(s))
	print(y * a + x * p)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	s = input()
	count_day = 0
	streak = 0
	max_days = -1
	sal = 0
	for word in s:
		if word == '1':
			count_day += 1
			streak += 1
			if max_days < streak:
				max_days = streak
		else:
			streak = 0
	sal = count_day * x + max_days * y
	print(sal)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	s = input()
	streak = 0
	cur = 0
	for i in s:
		if i == '1':
			cur = cur + 1
			streak = max(cur, streak)
		else:
			cur = 0
	a = s.count('1')
	print(a * x + streak * y)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	string = input()
	string += '0'
	maxi = -1
	l = 0
	c = 0
	for i in string:
		if int(i) == 1:
			c += 1
			l += 1
		else:
			if maxi < l:
				maxi = l
			l = 0
	print(c * x + maxi * y)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	if '1' in s:
		f = 1
	else:
		f = 0
	ma_x = 0
	ans = 0
	for j in range(29):
		if s[j] == '1':
			ans += n
			if s[j] == s[j + 1]:
				f += 1
				ma_x = max(f, ma_x)
			else:
				ma_x = max(ma_x, f)
				f = 1
	if s[-1] == '1':
		ans += n
	print(ans + m * ma_x)


for i in range(int(input())):
	(w, b) = map(int, input().split())
	s = input()
	streak = 1
	hstr = 0
	p = 0
	for i in range(len(s)):
		if s[i] == '1':
			p += 1
			if i - 1 >= 0 and s[i - 1] == '1':
				streak += 1
		else:
			hstr = max(hstr, streak)
			streak = 1
	hstr = max(hstr, streak)
	sal = p * w + b * hstr
	print(sal)


t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	s = input()
	c = 0
	m = 0
	a = 0
	for i in s:
		if i == '1':
			c += 1
	for i in range(len(s)):
		if s[i] == '1':
			a += 1
		else:
			m = max(m, a)
			a = 0
	m = max(m, a)
	tot = c * n + m * p
	print(tot)


for t in range(int(input())):
	(x, y) = map(int, input().split())
	l = input()
	ls = 0
	maxi = 0
	i = 0
	oc = 0
	while i < 30:
		if l[i] == '0':
			maxi = max(ls, maxi)
			ls = 0
			i = i + 1
			continue
		else:
			ls = ls + 1
			i = i + 1
			oc = oc + 1
	maxi = max(ls, maxi)
	print(oc * x + maxi * y)


q = int(input())
while q > 0:
	(x, y) = map(int, input().split())
	l = input()
	l = list(l)
	n = len(l)
	c = 0
	a = []
	for i in range(n - 1):
		if l[i] == '1' and l[i + 1] == '1':
			c = c + 1
		else:
			a.append(c + 1)
			c = 0
	a.append(c + 1)
	c1 = l.count('1')
	c2 = max(a)
	c2 = int(c2)
	res = c1 * x + c2 * y
	print(res)
	q = q - 1


for i in range(int(input())):
	(x, y) = map(int, input().split())
	count = 0
	nlst = []
	lst = list(map(int, input()))
	actual = lst.count(1)
	if lst[len(lst) - 1] != 0:
		lst.append(0)
	for i in range(len(lst)):
		if lst[i] == 1:
			count += 1
		else:
			nlst.append(count)
			count = 0
	print(actual * x + max(nlst) * y)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	s = input()
	a = s.count('1')
	(c, d) = (0, 0)
	for i in range(len(s)):
		if s[i] == '1':
			c += 1
		else:
			c = 0
		if c > d:
			d = c
	ans = a * x + d * y
	print(ans)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	a = input()
	b = a.count('1')
	c = 0
	d = 0
	for i in range(len(a)):
		if a[i] == '1':
			c += 1
		else:
			c = 0
		if c > d:
			d = c
	print(b * x + d * y)


for i in range(int(input())):
	(ml, c) = (-1, 0)
	(p, q) = map(int, input().split())
	s = input()
	r = s.count('1')
	u = r * p
	s1 = s.split('0')
	ls = len(max(s1, key=len))
	v = q * ls
	print(u + v)


for _ in range(int(input())):
	(X, Y) = map(int, input().split())
	arr = input()
	print(arr.count('1') * X + Y * max([len(x) for x in arr.split('0')]))


T = int(input())
for tc in range(T):
	(X, Y) = map(int, input().split(' '))
	s = input()
	c_1 = 0
	c_0 = 0
	c = 0
	ans = []
	for i in range(len(s)):
		if s[i] == '1':
			c_1 = c_1 + 1
		else:
			c_0 = c_0 + 1
	actual = c_1 * X
	for j in range(len(s)):
		if s[j] == '1':
			c = c + 1
			ans.append(c)
		else:
			c = 0
	bonus = max(ans) * Y
	print(actual + bonus)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	s = input()
	c = 0
	ma = 0
	for i in range(len(s)):
		if s[i] == '1' and i == len(s) - 1:
			ma += 1
			c = max(c, ma)
		elif s[i] == '1':
			ma += 1
			c = max(c, ma)
		else:
			c = max(c, ma)
			ma = 0
	print(s.count('1') * x + c * y)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	m = input()
	m += '0'
	s = 0
	t = 0
	for i in range(len(m)):
		if m[i] == '1':
			t += 1
		else:
			if t > s:
				s = t
			t = 0
	print(m.count('1') * x + s * y)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	st = input()
	max_len = 0
	no_of_working_days = 0
	count = 0
	for i in range(30):
		if st[i] == '1':
			no_of_working_days += 1
			count += 1
		else:
			max_len = max(max_len, count)
			count = 0
	max_len = max(count, max_len)
	print(x * no_of_working_days + y * max_len)


from collections import Counter
t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	s = input()
	sal = 0
	streak = 0
	mxstreak = 0
	for i in range(30):
		if s[i] == '1':
			sal += 1
			streak += 1
		mxstreak = max(mxstreak, streak)
		if s[i] == '0':
			streak = 0
	print(sal * x + mxstreak * y)


from collections import Counter
t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	s = input()
	ans = 0
	sal = 0
	bon = 0
	mx = 0
	for i in range(30):
		if s[i] == '1':
			sal += 1
			bon += 1
		mx = max(mx, bon)
		if s[i] == '0':
			bon = 0
	print(sal * x + mx * y)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	b = input()[:30]
	ones = b.count('1')
	salary1 = ones * x
	index = []
	count = 0
	c = []
	for i in b:
		if i != '0':
			count += 1
			c.append(count)
		else:
			count = 0
			continue
	salary2 = max(c) * y
	print(salary1 + salary2)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	s = input()
	sal = list(s).count('1') * x
	l = s.split('0')
	ms = max([len(i) for i in l])
	sal += ms * y
	print(sal)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	s = list(map(int, input().strip()))
	l = []
	c = 0
	for i in s:
		if i == 1:
			c += 1
		else:
			c = 0
		l.append(c)
	m = s.count(1)
	b = max(l)
	print(m * x + b * y)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	l = list(map(int, input().strip()))
	l1 = []
	co1 = 0
	for i in l:
		if i == 1:
			co1 += 1
		else:
			co1 = 0
		l1.append(co1)
	co = l.count(1)
	maxc = max(l1)
	print(co * x + maxc * y)


for _ in range(int(input())):
	(x, y) = map(int, input().split(' '))
	a = input()
	total_days = []
	bonus_days = []
	for i in a:
		if i == '1':
			total_days.append(i)
	i = 0
	count = 0
	while i < len(a):
		if a[i] == '1':
			count += 1
			i += 1
		else:
			count = 0
			i += 1
		bonus_days.append(count)
	print(len(total_days) * x + max(bonus_days) * y)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	s = input()
	p = s.count('1') * x
	ma = 0
	tem = 0
	for i in s:
		if i == '1':
			tem += 1
		elif tem > ma:
			ma = tem
			tem = 0
		else:
			tem = 0
	if tem > ma:
		ma = tem
		tem = 0
	print(ma * y + p)


t = int(input())
for ni in range(t):
	(x, y) = map(int, input().split())
	s = input()
	s1 = s.count('1')
	sal = s1 * x
	for i in range(30, 0, -1):
		x = '1' * i
		if x in s:
			sal = sal + y * i
			break
	print(sal)


for t in range(int(input())):
	(x, y) = map(int, input().split())
	s = input()
	s += '0'
	sal = b = 0
	bo = []
	for i in range(len(s)):
		if s[i] == '1':
			sal += 1
			b += 1
		else:
			bo.append(b)
			b = 0
	print(sal * x + max(bo) * y)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	l = list(map(int, input()))
	m = 0
	c = 0
	d = 0
	for i in l:
		if i == 1:
			c = c + 1
			d += 1
		elif d > m:
			m = d
			d = 0
		else:
			d = 0
	if d > m:
		m = d
	print(c * x + m * y)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	S = list(input())
	S.append('0')
	l = []
	c = 0
	for i in S:
		if i == '1':
			c += 1
		else:
			l.append(c)
			c = 0
	print(sum(l) * x + max(l) * y)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	s = input()
	c = 0
	for j in s:
		if j == '1':
			c += 1
	c *= x
	l = []
	j = 0
	while j < len(s):
		if s[j] == '1':
			k = 0
			while j < len(s) and s[j] == '1':
				k += 1
				if k not in l:
					l.append(k)
				j += 1
		else:
			j += 1
	if len(l) > 0:
		c += max(l) * y
	print(c)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	string = input()
	m = string.count('1')
	tmoney = 0
	tmoney += x * m
	arr = []
	c = 0
	for i in string:
		if i == '1':
			c += 1
		elif i == '0':
			if c == 0:
				continue
			else:
				arr.append(str(c))
				c = 0
	arr.append(str(c))
	arr = list(map(int, arr))
	s = max(arr)
	tmoney += y * s
	print(tmoney)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	work = list(input())
	day = work.count('1')
	salary = day * x
	bonus = []
	c = 0
	for i in range(len(work)):
		if work[i] == '1':
			c += 1
		else:
			c = 0
		bonus.append(c)
	bonus.sort()
	salary += y * bonus[-1]
	print(salary)


n = int(input())
for i in range(0, n):
	(x, y) = map(int, input().split())
	m = input()
	c = r = d = 0
	for i in m:
		if i == '1':
			c = c + 1
			d = d + 1
		else:
			d = 0
		if r < d:
			r = d
	print(x * c + y * r)


T = int(input())
for i in range(T):
	(x, y) = map(int, input().split())
	s = input()
	count = s.count('1')
	streak = max(map(len, s.split('0')))
	print(count * x + streak * y)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	s = input()
	pt = 0
	ct = 0
	rt = 0
	for j in s:
		if j == '1':
			pt += 1
			ct += 1
		else:
			ct = 0
		if rt < ct:
			rt = ct
	print(pt * x + rt * y)


n = int(input())
for _ in range(n):
	(dp, bonus) = map(int, input().split())
	l = input()
	bp = dp * l.count('1')
	if l.count('1') >= 1:
		length = 1
		i = 2
	ind = 0
	while ind < len(l):
		if l[ind:ind + i] == '1' * i:
			i += 1
			ind = 0
		else:
			ind += 1
	if length == 1:
		bp += bonus * (i - 1)
	print(bp)


for _ in range(int(input())):
	(X, Y) = map(int, input().split())
	string = input()
	ones = 0
	(streak, count) = (0, 0)
	for i in string:
		if i == '1':
			ones += 1
			count += 1
		else:
			count = 0
		if streak < count:
			streak = count
	print(X * ones + streak * Y)


t = int(input())
while t:
	(x, y) = map(int, input().split())
	s = input()
	p = s.count('1')
	q = max(map(len, s.split('0')))
	print(x * p + y * q)
	t -= 1


test = int(input())
for i in range(test):
	(salary, bouns) = map(int, input().split())
	List = input()
	count1 = List.count('1')
	count0 = List.count('0')
	List1 = List.split('0')
	okok = len(max(List1))
	total = count1 * salary + okok * bouns
	print(total)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	s = input()
	half = s.count('1')
	(maxx, c) = (0, 0)
	for i in range(0, len(s)):
		if s[i] == '1':
			c += 1
		else:
			c = 0
		maxx = max(maxx, c)
	print(maxx * y + half * x)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	bin_str = input()
	streak = 0
	total = 0
	temp_str = 0
	for i in bin_str:
		if i == '1':
			total += x
			temp_str += 1
		elif i == '0':
			if temp_str > streak:
				streak = temp_str
			temp_str = 0
	if temp_str > streak:
		streak = temp_str
	total += streak * y
	print(total)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	s = input()
	s = list(s)
	r = 0
	a = []
	k = 0
	for i in s:
		if i == '1':
			k = k + 1
		r = r + 1
		if i == '0':
			r = 0
		a.append(r)
	print(k * x + max(a) * y)


for t in range(int(input())):
	(x, y) = map(int, input().split(' '))
	s = input()
	c = s.count('1')
	m = 0
	l = []
	for i in range(30):
		if s[i] == '1':
			l.append(1)
		else:
			l = []
		m = max(m, len(l))
	ans = x * c + y * m
	print(ans)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	s = input() + '0'
	m = s.count('1')
	count = 0
	l = []
	for i in s:
		if i == '1':
			count += 1
		else:
			l.append(count)
			count = 0
	print(m * a + max(l) * b)


for _ in range(int(input())):
	(d, e) = map(int, input().split())
	s = input()
	a = s.count('1')
	s = s.split('0')
	s = max(list(map(lambda x: len(x), s)))
	print(a * d + s * e)