//doing with memoriziation
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<vector>
#define inf 1000000
#define lli long long int
char buf[1000];
char buf1[1000];
lli k,add,del,rem;
int arr[40][40];
lli min1(lli a,lli b)
{
if(a<b)
return a;
else
return b;
}
lli minimum(lli a,lli b,lli c)
{
return min1(min1(a,b),c);
}
lli edit_dis(char *buf,char*buf1,lli m,lli n,lli add1,lli del1,lli rem1)
{
if(add1+del1+rem1>k)//if edit is greater than k return inf
return inf;
if(m==0 && n==0)
{
return 0;
}
if(m==0 && n<k)
return n;
if(m==0 && n>k)//if edit is greater than k return inf
return inf;
if(n==0 && m<k)
return m;
if(n==0 && m>k)//if edit is greater than k return inf
return inf;
if(arr[m][n]!=-1)
{
return arr[m][n];
}
lli left;
if(arr[m-1][n]!=-1)
{
left=arr[m-1][n]+add;
add1=add+add1;
}
else
{
add1=add+add1;
left=edit_dis(buf,buf1,m-1,n,add1,del1,rem1)+add;
}
lli right;
if(arr[m][n-1]!=-1)
{
right=arr[m][n-1]+del;
del1=del1+del;
}
else
{
del1=del+del1;
right=edit_dis(buf,buf1,m,n-1,add1,del1,rem1)+del;
}
lli corner;
if(arr[m-1][n-1]!=-1)
{
corner=arr[m-1][n-1]+rem*(buf[m-1]!=buf1[n-1]);
rem1=rem1+rem;
}
else
{
rem1=rem1+rem;
corner=edit_dis(buf,buf1,m-1,n-1,add1,del1,rem1)+rem*(buf[m-1]!=buf1[n-1]);
}
return arr[m][n]=minimum(right,left,corner);
}
void my_memset()
{
lli i,j;
for(i=0;i<40;i++)
{
for(j=0;j<40;j++)
arr[i][j]=-1;
}
}
int main()
{
lli t;
getchar_unlocked();
while(t--)
{
my_memset();
getchar_unlocked();
getchar_unlocked();
scanf("%lld%lld%lld",&add
,&rem
,&k
); del=add;
lli ans=edit_dis(buf,buf1,m,n,0,0,0);
}
}
Ly9kb2luZyB3aXRoIG1lbW9yaXppYXRpb24KI2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RkbGliLmg+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2luY2x1ZGU8c3RyaW5nLmg+CiNpbmNsdWRlPHZlY3Rvcj4KI2RlZmluZSBpbmYgMTAwMDAwMAojZGVmaW5lIGxsaSBsb25nIGxvbmcgaW50CmNoYXIgYnVmWzEwMDBdOwpjaGFyIGJ1ZjFbMTAwMF07CmxsaSBrLGFkZCxkZWwscmVtOwppbnQgYXJyWzQwXVs0MF07CmxsaSBtaW4xKGxsaSBhLGxsaSBiKQp7CiAgaWYoYTxiKQogICAgcmV0dXJuIGE7CiAgZWxzZQogICAgcmV0dXJuIGI7Cn0KCmxsaSBtaW5pbXVtKGxsaSBhLGxsaSBiLGxsaSBjKQp7CiAgcmV0dXJuIG1pbjEobWluMShhLGIpLGMpOwp9CgoKbGxpIGVkaXRfZGlzKGNoYXIgKmJ1ZixjaGFyKmJ1ZjEsbGxpIG0sbGxpIG4sbGxpIGFkZDEsbGxpIGRlbDEsbGxpIHJlbTEpCnsKICBpZihhZGQxK2RlbDErcmVtMT5rKS8vaWYgZWRpdCBpcyBncmVhdGVyIHRoYW4gayByZXR1cm4gaW5mCiAgIHJldHVybiBpbmY7CiAgaWYobT09MCAmJiBuPT0wKQogIHsKICAgIHJldHVybiAwOwogIH0KICBpZihtPT0wICYmIG48aykKICAgIHJldHVybiBuOwogIGlmKG09PTAgJiYgbj5rKS8vaWYgZWRpdCBpcyBncmVhdGVyIHRoYW4gayByZXR1cm4gaW5mCiAgICByZXR1cm4gaW5mOwogIGlmKG49PTAgJiYgbTxrKQogICAgcmV0dXJuIG07CiAgaWYobj09MCAmJiBtPmspLy9pZiBlZGl0IGlzIGdyZWF0ZXIgdGhhbiBrIHJldHVybiBpbmYKICAgIHJldHVybiBpbmY7CiAgaWYoYXJyW21dW25dIT0tMSkKICB7CiAgICByZXR1cm4gYXJyW21dW25dOwogIH0KICBsbGkgbGVmdDsKICBpZihhcnJbbS0xXVtuXSE9LTEpCiAgewogICAgbGVmdD1hcnJbbS0xXVtuXSthZGQ7CiAgICBhZGQxPWFkZCthZGQxOwogIH0KICBlbHNlCiAgewogICAgIGFkZDE9YWRkK2FkZDE7CiAgICAgbGVmdD1lZGl0X2RpcyhidWYsYnVmMSxtLTEsbixhZGQxLGRlbDEscmVtMSkrYWRkOwogIH0KCgogIGxsaSByaWdodDsKICBpZihhcnJbbV1bbi0xXSE9LTEpCiAgewogICAgcmlnaHQ9YXJyW21dW24tMV0rZGVsOwogICAgZGVsMT1kZWwxK2RlbDsKICB9CiAgZWxzZQogIHsKICAgICBkZWwxPWRlbCtkZWwxOwogICAgIHJpZ2h0PWVkaXRfZGlzKGJ1ZixidWYxLG0sbi0xLGFkZDEsZGVsMSxyZW0xKStkZWw7CiAgfQoKICBsbGkgY29ybmVyOwogIGlmKGFyclttLTFdW24tMV0hPS0xKQogIHsKICAgIGNvcm5lcj1hcnJbbS0xXVtuLTFdK3JlbSooYnVmW20tMV0hPWJ1ZjFbbi0xXSk7CiAgICByZW0xPXJlbTErcmVtOwogIH0KICBlbHNlCiAgewogICAgIHJlbTE9cmVtMStyZW07CiAgICAgY29ybmVyPWVkaXRfZGlzKGJ1ZixidWYxLG0tMSxuLTEsYWRkMSxkZWwxLHJlbTEpK3JlbSooYnVmW20tMV0hPWJ1ZjFbbi0xXSk7CiAgfQoKICByZXR1cm4gYXJyW21dW25dPW1pbmltdW0ocmlnaHQsbGVmdCxjb3JuZXIpOwp9CnZvaWQgbXlfbWVtc2V0KCkKewogIGxsaSBpLGo7CiAgZm9yKGk9MDtpPDQwO2krKykKICB7CiAgICBmb3Ioaj0wO2o8NDA7aisrKQogICAgIGFycltpXVtqXT0tMTsKICB9Cn0KaW50IG1haW4oKQp7CiAgbGxpIHQ7CiAgc2NhbmYoIiVsbGQiLCZ0KTsKICBnZXRjaGFyX3VubG9ja2VkKCk7CiAgd2hpbGUodC0tKQogIHsKICAgIG15X21lbXNldCgpOwogICAgc2NhbmYoIiVzIixidWYpOwogICAgZ2V0Y2hhcl91bmxvY2tlZCgpOwogICAgc2NhbmYoIiVzIixidWYxKTsKICAgIGdldGNoYXJfdW5sb2NrZWQoKTsKICAgIHNjYW5mKCIlbGxkJWxsZCVsbGQiLCZhZGQsJnJlbSwmayk7CiAgICBkZWw9YWRkOwogICAgbGxpIG09c3RybGVuKGJ1Zik7CiAgICBsbGkgbj1zdHJsZW4oYnVmMSk7CiAgICBsbGkgYW5zPWVkaXRfZGlzKGJ1ZixidWYxLG0sbiwwLDAsMCk7CiAgICBwcmludGYoImFucz09PT0lbGxkXG4iLGFucyk7CiAgfQp9Cg==