码队的女朋友非常喜欢玩某款手游，她想让码队带他上分。但是码队可能不会带青铜段位的女朋友上分，因为码队的段位太高（已经到达王者），恐怕不能和他的女朋友匹配游戏。

码队的女朋友有些失落，她希望能尽快冲上王者。这个赛季开始了，求胜心切的码队的女朋友想让码队帮她计算一个问题：

这个赛季码队的女朋友一共打了 NN 场排位赛，每一场排位赛中，码队女朋友的成绩用 S_iSi​ 来表示（成绩只可能为“赢”或“输”。 11 代表码队女朋友赢了这场比赛，00 则代表输了这场比赛）。由于这款游戏使用净胜场数这个数据指标来衡量玩家能否晋级更高的段位（玩家净胜场数 = 玩家赢场数 - 玩家输场数），所以码队的女朋友想知道，这个赛季的过程中她的最高净胜场次。

码队听完他女朋友的问题之后，觉得她有些天真，因为码队知道，这家游戏厂商可能出于不想让玩家早“弃坑”的目的，所以在每个赛季都会给每位玩家发出 KK 张 「排位保护卡」。如果一名玩家在一场排位赛中输掉了游戏，但 TA 还有排位保护卡，那么系统将自动为 TA 用掉一张排位保护卡，帮该玩家抵消这场输掉的排位赛（即在系统记录成绩时，不将该局游戏计入玩家的输场数）。但是，如果一名玩家在某个赛季中，没有用完这 KK 张排位保护卡，那么这些剩余的排位保护卡将失效，不能在下个赛季继续使用。

听完码队说的这些事情以后，码队的女朋友变得更有信心了！现在，码队的女朋友想求助你：如果按照这个赛季的这 NN 场排位赛成绩来计算，经过 MM 个赛季（假设每个赛季都打 NN 场排位赛，且每个赛季都获得了完全相同的排位赛成绩），那在这 MM 个赛季过程中，她的最高净胜是多少场？

输入格式

第一行一个整数 TT，表示有几组数据（T \le 1000T≤1000）。

对于每一组测试数据：第一行有三个整数 N,K,MN,K,M，分别代表码队的女朋友在一个赛季里总共打了 NN 场排位赛，每个赛季有 KK 张排位保护卡，总共将进行 MM 个赛季，以空格分隔。（1\le K \le N \le 1001≤K≤N≤100，1 \le M \le 10^91≤M≤109）

接下来一行，输入一个长度为 NN 的字符串（只由 00 和 11 组成），代表码队的女朋友在一个赛季里的每场排位赛中的成绩 S_iSi​ (i=1,2, \cdots ,N)(i=1,2,⋯,N)。

输出格式

对于每一组测试数据，输出一行。

每行只包含一个整数，代表在 MM 个赛季过程中，码队的女朋友最高能净胜多少场游戏。如果净胜场数为负，请输出 00。

输出时每行末尾的多余空格，不影响答案正确性

样例输入1

1
5 1 2
11110

样例输出1

8

样例输入2

1
5 2 2
00101

样例输出2

2

坑点1：

那在这 M个赛季过程中，她的最高净胜是多少场？

最高净胜场其实是最后一个赛季里，截止到当前赛季净胜场最高的时候的总胜场

比如：

5个赛季，每个赛季的成绩是

11001

一个赛季总净胜场是 1+1-1-1+1=1

那么前四个月的总净胜场是4，然后最后一个赛季打完前两局，这时候净胜场是2，所以全部赛季里净胜场最高的时候是4+2=6

坑点2：

开long long

剩下的注意一下保护卡和负分就行了

代码：

#include<iostream>
#include<string>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
int main()
{
	ll t,n,k,m,i;
	string a;
	cin>>t;
	while(t--)
	{
		cin>>n>>k>>m;
		cin>>a;
		ll s=0;
		ll maxn=0;
		for(i=0;i<a.length();i++)
		{
			if(a[i]=='1')
				s++;
			else
			{
				if(k>0)
					k--;
				else
					s--;
			}
			if(maxn<s)
				maxn = s;
		}
		//cout<<maxn<<endl;
		if(s>=0)
			cout<<(s*(m-1)+maxn)<<endl;
		else
			cout<<0+maxn<<endl;
	}
	return 0;
}