#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
  int N, K;
  cin >> N >> K;
  vector<vector<int>> a(N, vector<int>(N));
  rep(i, N) rep(j, N) cin >> a[i][j];

  auto check = [=](int x) {
    vector<vector<int>> sum(N + 1, vector<int>(N + 1, 0));
    rep(i, N) rep(j, N) {
      sum[i + 1][j + 1] =
          sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + (a[i][j] <= x);
    }
    rep(i, N - K + 1) rep(j, N - K + 1) {
      int countNoMoreThanX =
          sum[i + K][j + K] - sum[i][j + K] - sum[i + K][j] + sum[i][j];
      if (countNoMoreThanX >= (K * K + 1) / 2) return true;
    }
    return false;
  };

  int ng = -1, ok = 1e9;
  while (ok - ng > 1) {
    int mid = (ng + ok) / 2;
    if (check(mid))
      ok = mid;
    else
      ng = mid;
  }
  cout << ok << endl;
}
#include <stdio.h>
int n, m, r, t, y, d, ans, f;
int w[8];
int b[8];
int c[8];
int l[100000];
int v[100000];
int x[256];
int main() {
	ans = 1000000000;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", w + i);
	}
	for (int i = 0; i < m; i++) {
		scanf("%d%d", l + i, v + i);
		for (int j = 0; j < n; j++) {
			if (v[i] < w[j])f = 1;
		}
	}
	if (f) {
		printf("-1\n");
		return 0;
	}
	r = 1 << n;
	for (int i = 0; i < r; i++) {
		t = i;
		y = 0;
		for (int j = 0; j < n; j++) {
			if (t & 1) {
				y += w[j];
			}
			t >>= 1;
		}
		for (int j = 0; j < m; j++) {
			if (y > v[j] && x[i] < l[j])x[i] = l[j];
		}
	}
	r = 1;
	for (int i = 1; i <= n; i++)r *= i;
	for (int i = 0; i < r; i++) {
		t = i;
		for (int j = 0; j < n; j++) {
			b[j] = -1;
			c[j] = 0;
		}
		for (int j = n; j; j--) {
			y = t % j + 1;
			d = 0;
			while (true) {
				if (b[d] == -1) {
					y--;
				}
				if (!y)break;
				d++;
			}
			b[d] = j - 1;
			t /= j;
		}
		for (int j = 1; j < n; j++) {
			c[j] = c[j - 1];
			y = 0;
			for (int k = j; k >= 0; k--) {
				y += 1 << b[k];
				if (x[y] > c[j] - c[k])c[j] = c[k] + x[y];
			}
		}
		if (ans > c[n - 1])ans = c[n - 1];
	}
	printf("%d\n", ans);
}