# include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 int n,len[maxn],l;

 char dic[maxn][];

 char s[];

 int dp[],leng,checkf;

 int f[][],c[][];

 void dfs (int x,int s,int r)

 {

     if(x==r+)

     {

         if(s>=&&leng%s==) checkf=;

         return ;

     }

     if(checkf) return;

     for (R i=x;i<=r;++i)

         if(c[x][i])

             dfs(i+,s+,r);

 }

 bool check (int l,int r)

 {

     if(f[l][r]!=-) return f[l][r];

     leng=r-l+;

     checkf=false;

     dfs(l,,r);

     f[l][r]=checkf;

     return f[l][r];

 }

 void init()

 {

     for (R i=;i<=l;++i)

         for (R j=;j<=i;++j)

         {

             int f=false;

             for (R k=;k<=n;++k)

             {

                 if(len[k]!=i-j+) continue;

                 int ff=true;

                 for (R z=;z<=len[k];++z)

                     if(s[j+z-]!=dic[k][z]) ff=false;

                 if(ff) f=true;

                 if(f) break;

             }

             if(f) c[j][i]=;

         }

 }

 int main()

 {

     freopen("xgy.in","r",stdin);

     freopen("xgy.out","w",stdout);

     scanf("%d",&n);

     memset(f,-,sizeof(f));

     for (R i=;i<=n;++i)

     {

         scanf("%s",dic[i]+);

         len[i]=strlen(dic[i]+);

         for (R j=;j<=len[i];++j)

             if(dic[i][j]>='A'&&dic[i][j]<='Z') dic[i][j]=dic[i][j]-'A'+'a';

     }

     scanf("%s",s+);

     l=strlen(s+);

     for (R i=;i<=l;++i)

         if(s[i]>='A'&&s[i]<='Z') s[i]=s[i]-'A'+'a';

     init();

     for (R i=;i<=l;++i)

         dp[i]=-;

     dp[]=;

     for (R i=;i<=l;++i)

         for (R j=;j<i;++j)

         {

             if(dp[j]==-) continue;

             if(i-j+>) continue;

             if(check(j+,i)) dp[i]=max(dp[i],dp[j]+);

         }

     printf("%d\n",dp[l]);

     fclose(stdin);

     fclose(stdout);

     return ;

 }

 # include <cstdio>

 # include <iostream>

 # include <cstring>

 # include <string>

 # include <algorithm>

 # include <cmath>

 # define R register int

 # define ll long long

 using namespace std;

 const int maxn=;

 int k,V,n;

 int w[maxn],v[maxn];

 int dp[][];

 int a[maxn];

 int main()

 {

     freopen("bag.in","r",stdin);

     freopen("bag.out","w",stdout);

     scanf("%d%d%d",&k,&V,&n);

     for (R i=;i<=n;++i) scanf("%d%d",&w[i],&v[i]);

     memset(dp,,sizeof(dp));

     dp[][]=;

     for (R i=;i<=n;++i)

         for (R j=V;j>=w[i];--j)

         {

             for (R z=;z<=k;++z)

             {

                 int T=dp[z][ j-w[i] ]+v[i];

                 if(T<) continue;

                 for (R l=z;l<=k;++l)

                     if(T>dp[l][j])

                     {

                         for (R t=k;t>l;--t)

                             dp[t][j]=dp[t-][j];

                         dp[l][j]=T;

                         break;

                     }

             }

         }

     int ans=;

     for (R i=;i<=k;++i) ans+=dp[i][V];

     printf("%d",ans);

     fclose(stdin);

     fclose(stdout);

     return ;

 }

 # include <cstdio>

 # include <iostream>

 # include <map>

 # include <algorithm>

 # include <bitset>

 # include <queue>

 # define R register int

 using namespace std;

 const int dx[]={-,,,};

 const int dy[]={,-,,};

 const int maxn=;

 const int knc=;

 int n,N,M;

 map <int,int> m;

 int x[maxn],y[maxn],sx,sy,ex,ey,a[maxn],b[maxn],c[maxn],d[maxn];

 bool ic[knc][knc],vis[knc][knc];

 struct node

 {

     int x,y,v;

 };

 queue <node> q;

 int bfs ()

 {

     node a,b;

     a.x=sx,a.y=sy,a.v=;

     q.push(a);

     while(q.size())

     {

         a=q.front();

         q.pop();

         int x=a.x,y=a.y;

         vis[x][y]=;

         if(a.x==ex&&a.y==ey) return a.v;

         for (R d=;d<;++d)

         {

             x=a.x,y=a.y;

             while(ic[x][y]==)

             {

                 x+=dx[d],y+=dy[d];

                 if(x>N||y>M||x<||y<) break;

                 if(x==ex&&y==ey)

                     return a.v+;

             }

             if(x>N||y>M||x<||y<) continue;

             if(!ic[x][y]) continue;

             x-=dx[d],y-=dy[d];

             if(vis[x][y]) continue;

             vis[x][y]=;

             b.x=x,b.y=y,b.v=a.v+;

             q.push(b);

         }

     }

     return ;

 }

 int read ()

 {

     R x=,f=;

     char c=getchar();

     while(!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }

     while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

     return x*f;

 }

 int main()

 {

     freopen("ice.in","r",stdin);

     freopen("ice.out","w",stdout);

     n=read();

     sx=read(),sy=read(),ex=read(),ey=read();

     x[++x[]]=sx,x[++x[]]=ex;

     y[++y[]]=sy,y[++y[]]=ey;

     for (R i=;i<=n;++i)

     {

         a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();

         x[++x[]]=a[i],x[++x[]]=c[i];

         y[++y[]]=b[i],y[++y[]]=d[i];

     }

     sort(x+,x++x[]);

     sort(y+,y++y[]);

     int cnt=;

     for (R i=;i<=x[];++i)

     {

         if(x[i]!=x[i-]||i==) cnt++;

         m[ x[i] ]=cnt;

     }

     N=cnt;

     for (R i=;i<=n;++i)

         a[i]=m[ a[i] ],c[i]=m[ c[i] ];

     sx=m[sx],ex=m[ex];

     cnt=;

     m.clear();

     for (R i=;i<=y[];++i)

     {

         if(y[i]!=y[i-]||i==) cnt++;

         m[ y[i] ]=cnt;

     }

     M=cnt;

     for (R i=;i<=n;++i)

         b[i]=m[ b[i] ],d[i]=m[ d[i] ];

     sy=m[sy],ey=m[ey];

     for (R i=;i<=n;++i)

         for (R j=a[i];j<=c[i];++j)

             for (R z=b[i];z<=d[i];++z)

                 ic[j][z]=;

     printf("%d",bfs());

     fclose(stdin);

     fclose(stdout);

     return ;

 }