#include <assert.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stdio.h>
#include <sstream>
#include <cstring>

using namespace std;

#define Size(x) (int)(x).size()
#define For(i,a,b) for(int i=(int)(a);i<=(int)(b);++i)
#define Ford(i,a,b) for(int i=(int)(a);i>=(int)(b);--i) 
#define RepV(i,v) for (int i=0;i<Size(v);++i)
#define All(c) (c).begin(),(c).end()
#define Fill(a,b) memset(&a,b,sizeof(a))
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define Abs(a) ((a)<0?-(a):(a))

// Max-Flow (Another based on Push-Relabel)
// written by Pavel Kuznetsov

const int maxn=210;
const int INF=1000000000;


int f[maxn][maxn], c[maxn][maxn], h[maxn];
int a[maxn][maxn], cur[maxn], e[maxn];
deque <int> q;

void lift(int u){
   int minh=INF;
   For(i,1,a[u][0]) {
      int v=a[u][i];
      if (c[u][v]-f[u][v]>0) minh=min(minh,h[v]);
   }
   h[u]=minh+1;
}

void push(int u, int v){
   int d=min(c[u][v]-f[u][v],e[u]);
   e[u]-=d; f[u][v]+=d; f[v][u]=-f[u][v]; e[v]+=d;
}

void relax(int u){
   while (e[u]>0) {
     int v=a[u][cur[u]];
     if (cur[u]>a[u][0]) {
      lift(u);
      cur[u]=1;
     } else if (c[u][v]-f[u][v]>0 && h[u]==h[v]+1) {
      push(u,v);
      q.push_back(v);
      ++cur[u];
     } else ++cur[u];
   }
}

int max_flow(int s, int t, int vertex_low, int vertex_high){
   // Initialization
   int N=vertex_high-vertex_low+1;
   Fill(f,0); Fill(h,0); Fill(e,0); Fill(a,0);
   h[s]=N;
   For(i,vertex_low,vertex_high)
     For(j,vertex_low,vertex_high) 
       if (c[i][j]>0 || c[j][i]>0) a[i][++a[i][0]]=j;
   For(i,vertex_low,vertex_high) cur[i]=1;
   q.clear();
   For(i,1,a[s][0]) {
      int v=a[s][i];
      f[s][v]=c[s][v];
      f[v][s]=-f[s][v];
      e[v]=c[s][v];
      q.push_back(v);
   }
   while (!q.empty()) {
      int u=q.front(); q.pop_front();
      if (u==s || u==t) continue;
      relax(u);
   }
   return e[t];
}

const int MAXN = 30;

int n, m[MAXN], begin[MAXN], end[MAXN], t[MAXN][MAXN];

int main(){
//   freopen("input.txt","rt",stdin);
//   freopen("output.txt","wt",stdout);
   
   // Input data
   scanf("%d",&n);
   
   assert(n>=1 && n<=20);
   
   For(i,1,n) {
      scanf("%d",&m[i]);
      assert(m[i]>=1 && m[i]<=50);
   }
   For(i,1,n) {
      int h1, h2, m1, m2;
      scanf("%d:%d %d:%d",&h1,&m1,&h2,&m2);
      assert(h1>=0 && h1<=23 && m1>=0 && m1<=59 && h2>=0 && h2<=23 && m2>=0 && m2<=59);
      begin[i] = h1*60+m1; end[i] = h2*60+m2;
      assert(end[i]-begin[i]>=1);
   }
   
   For(i,1,n) For(j,1,n) {
      scanf("%d",&t[i][j]);
      assert(t[i][j]>=0 && t[i][j] <= 24*60);
   }
   
   // Solving
   
   int st = 0, fn = 2*n+1;
   
   Fill(c,0);
   For(i,1,n) c[st][i] = INF, c[n+i][fn]=INF, c[i][n+i]=INF;
   For(i,1,n) For(j,1,n) if (end[i] + t[i][j] <= begin[j]) c[n+i][j]=INF;
   
   For(i,1,n) c[i][n+i] -= m[i];
   c[fn][st]=INF;
   
   int st2=fn+1, fn2=fn+2;
   For(i,1,n) c[st2][n+i]=m[i], c[i][fn2]=m[i];
   
   max_flow(st2,fn2,st,fn2);
   
   // Assertion: feasible flow should always exist in given network!
   For(i,1,n) assert( f[st2][n+i]==m[i] );
   
   c[fn][st]=0; f[fn][st]=0; f[st][fn]=0;
   For(i,1,n) c[i][n+i] += m[i], f[i][n+i]+=m[i], f[n+i][i]-=m[i];
   
   int mf=0;
   For(i,1,n) mf += f[st][i];
   
   For(i,st,fn) For(j,st,fn) assert( f[i][j]+f[j][i]==0 );
   
   For(i,st,fn) For(j,st,fn) if (f[i][j] > 0) {
      c[i][j] = INF-f[i][j];
      c[j][i] = f[i][j] - (i>=1 && i<=n ? m[i] : 0);
   }
   
   mf -= max_flow(fn,st,st,fn);
   
   // Output data
   
   cout << mf;
   
   return 0;
}
