// 解き直し.
// https://atcoder.jp/contests/arc105/editorial/170
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
LL cW[11], bL[101010], bV[101010];

struct bridge{
    LL l, v; // 長さ, 耐荷重.
    bool operator < (const bridge& rhs) const{
        return (v != rhs.v) ? (v > rhs.v) : (l < rhs.l);
    }
};

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    LL maxW = 0, minV = 202020202020202020;
    rep(i, N){
        scanf("%lld", &cW[i]);
        maxW = max(maxW, cW[i]);
    }
    priority_queue<bridge> pq;
    rep(i, M){
        LL l, v;
        scanf("%lld %lld", &l, &v);
        minV = min(minV, v);
        pq.push({l, v});
    }
    
    // 2. 橋が崩落するパターンを除外.
    if(maxW > minV){
        puts("-1");
        return 0;
    }
    
    // 3. 橋の耐荷重に対する必要な最小間隔を保存.
    int idx = 0;
    while(!pq.empty()){
        bridge b = pq.top();
        pq.pop();
        // printf("b.l=%lld b.v=%lld\n", b.l, b.v);
        bL[idx + 1] = max(bL[idx], b.l);
        bV[idx + 1] = b.v;
        idx++;
    }
    // rep(i, M + 1) printf("l=%lld v=%lld\n", bL[i], bV[i]);
    
    // 4. ラクダの隊列を全探索.
    vector<int> z(N);
    iota(all(z), 0);
    LL ans = -202020202020202020;
    do{
        // 4-1. ラクダの隊列の重量(累積和).
        LL cWCum[N + 1];
        memset(cWCum, 0LL, sizeof(cWCum));
        rep(i, N) cWCum[i + 1] = cWCum[i] + cW[z[i]];
        // rep(i, N) printf("%d ", z[i]);
        // puts("");
        // rep(i, N + 1) printf("%lld ", cWCum[i]);
        // puts("");
        
        // 4-2. 制約.
        LL x[N][N];
        memset(x, 0LL, sizeof(x));
        rep(i, N){
            repx(j, i + 1, N){
                int at = lower_bound(bV, bV + M + 1, cWCum[j + 1] - cWCum[i]) - bV - 1;
                x[i][j] = max(x[i][j], bL[at]);
                x[j][i] = x[i][j];
            }
        }
        // rep(i, N){
        //     repx(j, i + 1, N) printf("%lld ", x[i][j]);
        //     puts("");
        // }
        
        // 4-3. グラフの最長路の長さは？
        // ex.
        // AtCoder Beginner Contest 022 (C - Blue Bird) を ベース に 実装.
        // https://atcoder.jp/contests/abc022/tasks/abc022_c
        // -> 具体的には, Warshall–Floyd法で, 
        // repx(k, 1, N) repx(i, 1, N) repx(j, 1, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        // とあるものを, i = 0 に 固定するイメージで, 更新する形に変更.
        LL g[N][N], way = 0;
        memset(g, 0LL, sizeof(g));
        repx(i, 1, N){
            rep(j, i + 1){
                g[0][i] = min(g[0][i], g[0][j] - x[i][j]);
                way = min(way, g[0][i]);
                // printf("i=%d j=%d %lld \n", i, j, x[i][j]);
            }
        }
        
        // 4-4. 最長路の長さについて, 最小値を更新.
        ans = max(ans, way);
    }while(next_permutation(all(z)));
    
    // 5. 出力.
    printf("%lld\n", -ans);
    return 0;
    
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define mat vector<vector<int>>
const int inf = 1 << 30;
const ll mod = 1e9 + 7;
const ll linf = 1LL << 62;
const db EPS = 1e-7;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

int N, K;
int A[810][810];
int cnt[810][810];

int main() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> A[i][j];
        }
    }
    int lb = -1, ub = 1e9 + 1;
    while (ub - lb > 1) {
        int mid = (ub + lb) / 2;
        for (int i = 1; i <= N ; i++) {
            for (int j = 1; j <= N; j++) {
                cnt[i][j] = (A[i][j] <= mid);
            }
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                cnt[i][j + 1] += cnt[i][j]; 
            }
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                cnt[i + 1][j] += cnt[i][j];
            }
        }
        bool flag = false;
        for (int i = K; i <= N; i++) {
            for (int j = K; j <= N; j++) {
                int aa = cnt[i][j] - cnt[i - K][j] - cnt[i][j - K] + cnt[i - K][j - K];
                if (aa >= (K * K) - ((K * K) / 2)) flag = true;
            }
        }
        if (flag) ub = mid;
        else lb = mid;
    }
    cout << ub << endl;
}