作为一名屌丝程序员，机械键盘是哈利梦寐以求的神器。终于，在除夕夜的时候，他爸爸送了他一个机械键盘。
哈利的键盘与我们平常所见到的的键盘不一样，我们可以认为他的键盘是一个500*500的矩形，其中26个字母键分布在某些格点上。这天，心血来潮的哈利想用他心爱的键盘写一些代码，假设他的代码只有一行，而且都是由小写的英文字母构成。由于键盘上的按键分布在不同的地方，哈利码代码时，移动手指要花费一些能量，其花费能量为上一次敲击的键，与当前要敲的键的曼哈顿距离。为了节省力气，哈利可以不必完全按照要敲的代码输入，他可以跳着输，比如helloworld，他可以按照d r o o l l l e h w的顺序输入，但是为了让输入的代码是他想要的输入顺序，在输入的过程中，他可能需要移动光标，在相应的位置输入对应的单词，作为一名熟练的vim选手，哈利将光标移动一个位置仅需1的费用，比如他想输入qpy，他按q->y->p的顺序输入，那么花费的总的能量为cost(q,y)+1+cost(y,p)，其中cost(x,y)为字母x,y之间的曼哈顿距离，当中花费的1的能量为输入y后，往左移动一次光标所花费的能量。当然，人的记忆力都是有限的，哈利最多只能记住连续10个位置的字母有没有输入过，也就是说如果想输入第i个字符，要么i<=10或者所有第i-10(包含)以前的字符都已经输入，比如第1个位置的字母还没有输，他就不能考虑第11个字母，因为一旦考虑第11个字母的时候，他就忘了第1个字母有没有输了。现在哈利想知道，他敲完这篇代码，最少需要多少能量？哈利第一次输入的时候可以不花费能量。
Input
前26行，每行两个整数x, y (0<=x<500, 0<=y<500)以空格分开，表示26个英文字母键a-z所在位置，保证不会有两个键在相同的位置
第27行为一个长度不超过100的字符串(非空)，表示哈利要敲的代码，由小写字母a-z组成
Output
输出一个整数，表示哈利敲完代码最少花多少能量
状压DP。f[i][j][zt]表示考虑了前i位（i-10以前的都填完了），在最后10位里的第j位，最后10位里是否填了数的状态为zt。
转移的话，一种是从j挪到最后10位里的另外一个未填的位，另一种是从j挪到第i+x位，要求x<=10且i-10..i-10+x都填了。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define ui unsigned int
#define ull unsigned long long
const int maxn=,inf=;
int f[][][];
int dis[][][],map[][],x[],y[];
int i,j,k,n,m;
char s[],s1[]; int ra,fh;char rx;
inline int read(){
rx=getchar(),ra=,fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')fh=-,rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
} inline void mins(int &a,int b){if(b<a)a=b;}
inline int run(int n){
int i,j,_j,zt;register int j1,_j1,zt1;int mx=<<,nowf;
// for(i=1;i<=n;i++)printf("%c",s[i]+'a'-1);puts("");
for(i=;i<=n;i++)memset(f[i],,sizeof(f[i]));
for(i=;i<;i++)f[][i][<<i]=; for(i=;i<=n;i++)for(zt=;zt<mx;zt++)for(j=,_j=i-+j;j<;j++,_j++)if(zt&(<<j)){
nowf=f[i][j][zt];
for(j1=,_j1=i-+j1;j1<;j1++,_j1++)if(!(zt&(<<j1)))
mins(f[i][j1][zt|(<<j1)],nowf+map[s[_j]][s[_j1]]+dis[zt][j][j1]);
for(j1=,_j1=i++j1,zt1=zt>>;j1<&&(zt&(<<j1))&&_j1<=n;j1++,_j1++,zt1>>=)
mins(f[_j1][][zt1|(<<)],nowf+map[s[_j]][s[_j1]]+dis[zt][j][]);
}
int ans=<<;
for(i=;i<;i++)mins(ans,f[n][i][mx-]);
// printf(" %d\n",ans);
return ans;
}
inline int abs(int x){return x<?-x:x;}
int main(){
int mx=<<;
for(i=;i<mx;i++)for(j=;j<;j++)if(i&(<<j))for(k=;k<;k++)if(!(i&(<<k))){
int a=j,b=k;if(a>b)std::swap(a,b);
for(int i1=a+;i1<b;i1++)if(i&(<<i1))dis[i][j][k]++;
dis[i][j][k]+=k<j;
} for(i=;i<=;i++){
x[i]=read(),y[i]=read();
for(j=;j<=i;j++)map[i][j]=map[j][i]=abs(x[i]-x[j])+abs(y[i]-y[j]);
}
scanf("%s",s+),n=strlen(s+);
for(i=;i<=n;i++)s[i]-='a'-; if(n>=)return printf("%d\n",run(n)),;
for(i=;i<=n;i++)s1[i+-n]=s[i];
int ans=<<;
for(i=;i<=;i++){
for(j=;j<=-n;j++)s1[j]=i;
memcpy(s,s1,sizeof(s1));
mins(ans,run());
}
printf("%d\n",ans);
}