/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */


#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class EPeddler {
public:

    vector<int> graph[200005];

    void solve(istream& cin, ostream& cout) {
      SPEED;
      int n, m; cin >> n >> m;
      vector<ll> a(n);
      rep(i, n) {
        cin >> a[i];
      }
      vector<int> x(m), y(m);
      rep(i, m) {
        cin >> x[i] >> y[i];
        x[i]--; y[i]--;
        graph[x[i]].push_back(y[i]);
      }

      vector<ll> dp(n, LLONG_MIN/2);
      vector<ll> lowest(n, LLONG_MAX/2);

      for(int i=0; i<n; i++) {
        for(auto e: graph[i]) {
          chmin(lowest[e], lowest[i]);
          chmin(lowest[e], a[i]);
        }
      }

      ll ret = LLONG_MIN/2;
      for(int i=0; i<n; i++) {
        chmax(ret, a[i] - lowest[i]);
      }

      cout << ret << endl;
    }
};

signed main() {
  EPeddler solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 100005;

int n, d;
int a[N], b[N];

int minu[N];

vector<int> v[N];

void solv()
{
    scanf("%d%d", &n, &d);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &b[i]);

    a[n + 1] = b[n + 1] = d + 1;

    for (int i = 1; i <= n; ++i)
        minu[i] = N;

    map<int, int> mp;
    for (int i = 0; i <= n + 1; ++i)
    {
        mp[a[i] - i] = i;
        if (mp.find(b[i] - i) != mp.end())
        {
            if (mp[b[i] - i] != i)
                v[mp[b[i] - i]].push_back(i);
            minu[i] = min(minu[i], i - mp[b[i] - i]);
        }
    }

    mp.clear();
    for (int i = n + 1; i >= 0; --i)
    {
        mp[a[i] - i] = i;
        if (mp.find(b[i] - i) != mp.end())
        {
            if (mp[b[i] - i] != i)
                v[mp[b[i] - i]].push_back(i);
            minu[i] = min(minu[i], mp[b[i] - i] - i);
        }
    }

    for (int i = 0; i <= n + 1; ++i)
    {
        if (minu[i] == N)
        {
            printf("-1\n");
            return;
        }
    }

    ll ans = 0;
    for (int i = 0; i <= n + 1; ++i)
    {
        if (v[i].empty())
            continue;
        sort(all(v[i]));
        if (v[i][0] < i)
            ans += (i - v[i][0]);
        if (v[i].back() > i)
            ans += (v[i].back() - i);
    }

    printf("%lld\n", ans);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    solv();
    return 0;
}
