#pragma region Macros
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define REP2(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; ++i)
#define REP3(i, l, r) for (int i = (l), i##_len = (int)(r); i < i##_len; ++i)
#define GET_MACRO_REP(_1, _2, _3, NAME, ...) NAME
#define REP(...) GET_MACRO_REP(__VA_ARGS__, REP3, REP2) (__VA_ARGS__)
#define RREP2(i, n) for (int i = (n - 1); i >= 0; --i)
#define RREP3(i, l, r) for (int i = (r - 1), i##_len = (l); i >= i##_len; --i)
#define GET_MACRO_RREP(_1, _2, _3, NAME, ...) NAME
#define RREP(...) GET_MACRO_REP(__VA_ARGS__, RREP3, RREP2) (__VA_ARGS__)
#define IN(type, n) type n; cin >> n
#define INALL(v) for (auto &e : v) { cin >> e; }
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

#ifdef _DEBUG
#define DEBUG(x) cout << #x << ": " << x << endl
#else
#define DEBUG(x)
#endif

template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
void yes() { cout << "Yes" << endl; }
void no() { cout << "No" << endl; }
#pragma endregion

int main() {
  IN(int, N);
  IN(int, M);
  vector<ll> As(N);
  INALL(As);
  vector<vector<int> > citis(N, vector<int>());
  REP(i, M) {
    IN(int, X);
    IN(int, Y);
    X--;
    Y--;
    citis.at(Y).emplace_back(X);
  }

  vector<ll> maxs(N, -10000000000);
  RREP(i, N) {
    for (auto &city : citis.at(i)) {
      chmax(maxs.at(city), max(As.at(i), maxs.at(i)));
    }
  }

  ll ans = -10000000000;
  REP(i, N) {
    chmax(ans, maxs.at(i) - As.at(i));
    // cout << "i: " << i << ", A: " << As.at(i) << ", max: " << maxs.at(i) << ", cal: " << maxs.at(i) - As.at(i) << ", ans: " << ans << endl;
  }

  cout << ans << endl;

  return 0;
}

#include <bits/stdc++.h>      
using namespace std;            

#define  int               long long int
#define  ld                long double
#define  f(i,j,n)            for(int i = j; i <= n; i++)
#define  r(i,n,j)           for(int i = n; i >= j; i--)
#define  all(container)       container.begin() , container.end()
#define  sz(container)        (int)container.size()
#define  ff                first
#define  ss                second
#define  pii               pair <int , int>
#define  sp(x)              setprecision(x)
#define  mod              1000000007
#define  endl            "\n"
#define  pb              push_back
#define  mp             make_pair
#define  T             int ttt; cin >> ttt; while(ttt--)
#define fast           ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);

int power(int x, int y, int p)  
{  
    int res = 1;    
    x = x % p; 
    if (x == 0) return 0; 
    while (y > 0)  
    {     
        if (y & 1)  
            res = (res*x) % p;  
        y = y>>1; 
        x = (x*x) % p;  
    }  
    return res; 
}
int n,e,a[18][3],dp[18][600005];
int solve(int i,int mask){
    if(mask==e)   return ( abs(a[0][0]-a[i][0]) + abs(a[0][1]-a[i][1]) + max(0LL ,a[0][2]-a[i][2]));
    int &x = dp[i][mask];
    if(x!=1e18)  return x;
    f(j,0,n-1)
    {
        if( (mask & (1LL<<j)) ==0){
            int c= abs(a[j][0]-a[i][0]) + abs(a[i][1]-a[j][1]) + max(0LL ,a[j][2]-a[i][2]);
            x =min(x,solve(j,mask ^ (1LL<<j) ) + c);
        }
    }
    return x;
}

int32_t main()
{
    fast
    cin>>n;
    e= 1ll<<n;  e--;
    f(i,0,n)
        f(j,0,e)
            dp[i][j]=1e18;
    f(i,0,n-1)
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    cout<<solve(0,1LL<<0LL)<<endl;
}