## Editorial for BLAST

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const fi='';
fo='';
maxn=2001;
var n,m,k:longint;
f:array[0..maxn,0..maxn] of longint;
a,b:array[1..maxn] of char;
s:array['a'..'z','a'..'z'] of longint;

procedure rf;
var i:longint; p,q:char;
begin
assign(input,fi);
reset(input);
m:=0;
while not eoln do
begin
inc(m);
end;
n:=0;
while not eoln do
begin
inc(n);
end;
for p:='a' to 'z' do
for q:='a' to 'z' do
s[p,q]:=abs(ord(p)-ord(q));
close(input);
end;

function min(a,b,c:longint):longint;
begin
if (a<b) and (a<c) then min:=a
else
begin
if b<c then min:=b else min:=c;
end;
end;

procedure pr;
var i,j:longint;
begin
for i:=0 to n do f[0,i]:=i*k;
for i:=0 to m do f[i,0]:=i*k;
for i:=1 to m do
for j:=1 to n do
f[i,j]:=min(f[i-1,j-1]+s[a[i],b[j]],f[i-1,j]+k,f[i,j-1]+k);
end;

procedure wf;
begin
assign(output,fo);
rewrite(output);
write(f[m,n]);
close(output);
end;

begin
rf;
pr;
wf;
end.


#### Code mẫu của happyboy99x

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 2000+5;
char s[N], t[N];
int k, f[N][N];

int main() {
scanf("%s%s%d",s+1,t+1,&k);
int n = strlen(s+1), m = strlen(t+1);
for(int i = 1; i <= n; ++i) f[i][0] = k * i;
for(int j = 1; j <= m; ++j) f[0][j] = k * j;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
f[i][j] = min(abs(s[i] - t[j]) + f[i-1][j-1], k + min(f[i][j-1], f[i-1][j]));
printf("%d\n", f[n][m]);
return 0;
}


program mblast;
uses    math;
const   fi='';
maxN=2345;
var     f:array[0..maxN,0..maxN] of longint;
a,b:ansistring;
k:longint;

procedure input;
var     inp:text;
t:ansistring;
begin
assign(inp,fi);
reset(inp);
close(inp);
end;

procedure dp;
var     i,j:longint;
begin
f[0,0]:=0;
for i:=0 to length(a) do
for j:=0 to length(b) do
begin
if (i=0) and (j=0) then continue;
if i=0 then f[i,j]:=f[i,j-1]+k
else
if j=0 then f[i,j]:=f[i-1,j]+k
else
f[i,j]:=min(min(f[i-1,j]+k,f[i,j-1]+k),f[i-1,j-1]+abs(ord(a[i])-ord(b[j])));
end;
end;

begin
input;
dp;
write(f[length(a),length(b)]);
end.


#### Code mẫu của RR

//Written by RR
{$R+,Q+} {$Mode objFPC}
uses math;
const
FINP          =       {$IFDEF RR} 'input.txt'; {$ELSE} ''; {$ENDIF} FOUT = {$IFDEF RR} 'output.txt'; {$ELSE} ''; {$ENDIF}
MAXN          =       2222;
var
f1,f2         :       text;
a,b           :       ansistring;
f             :       array[0..MAXN,0..MAXN] of longint;
m,n,cost      :       longint;

procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure inp;
begin
end;
procedure solve;
var
i,j:longint;
begin
for i:=1 to m do
f[i,0]:=cost*i;
for i:=1 to n do
f[0,i]:=cost*i;
for i:=1 to m do
for j:=1 to n do
f[i,j]:=min(f[i-1,j-1]+abs(ord(a[i])-ord(b[j])),
min(f[i-1,j],f[i,j-1])+cost);

writeln(f2,f[m,n]);
end;

begin
openF;
inp;
solve;
closeF;
end.


#### Code mẫu của hieult

#include <cstdio>
//#include <conio.h>
#include <cstring>

using namespace std;

int s[2020][2020];
char s1[2020],s2[2020];
int blank;

int TTD(int x) { return x>0 ? x: -x;}

int main()
{
int s1len,s2len,i,j;
scanf("%s %s %d",s1,s2,&blank);
s1len = strlen(s1);
s2len = strlen(s2);
s[0][0] = 0;
for(j = 1;j<= s2len; j++) s[0][j] = s[0][j-1] + blank;
for(i = 1;i<= s1len; i++)
{
s[i][0] = s[i-1][0] + blank;
for(j = 1;j<=s2len;j++)
{
s[i][j] = s[i-1][j-1]+TTD(s1[i-1]-s2[j-1]);
if(s[i-1][j]+blank<s[i][j]) s[i][j] = s[i-1][j]+blank;
if(s[i][j-1]+blank<s[i][j]) s[i][j] = s[i][j-1]+blank ;
}
}
printf("%d\n",s[s1len][s2len]);
//getch();
}


#### Code mẫu của ll931110

{\$MODE DELPHI}
Program MBLAST;
Const
input  = '';
output = '';
maxn = 2000;
Var
a,b: string;
la,lb: integer;
F: array[0..maxn,0..maxn] of integer;
k: integer;

Procedure init;
Var
fi: text;
Begin
Assign(fi, input);
Reset(fi);

la:= length(a);

lb:= length(b);

Close(fi);
End;

Procedure optimize;
Var
i,j,t: integer;
Begin
For i:= 0 to la do F[i,0]:= i * k;
For i:= 0 to lb do F[0,i]:= i * k;

For i:= 1 to la do
For j:= 1 to lb do
Begin
F[i,j]:= F[i,j - 1] + k;

t:= F[i - 1,j] + k;
If F[i,j] > t then F[i,j]:= t;

t:= F[i - 1,j - 1] + abs(ord(a[i]) - ord(b[j]));
IF F[i,j] > t then F[i,j]:= t;
End;
End;

Procedure printresult;
Var
fo: text;
Begin
Assign(fo, output);
Rewrite(fo);
Writeln(fo, F[la,lb]);
Close(fo);
End;

Begin
init;
optimize;
printresult;
End.