#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define rep2(i, a)for(auto i : a)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x, std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
#define INF (1ll << 60)
ll mod = 1000000007;
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p & 1)a *= x; x *= x; p >>= 1; }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p & 1)a = a * x % mod;  x = x * x % mod; p >>= 1; }return a; }
ll co(ll n, ll k) { ll a = 1; rep(i, 1ll, k + 1) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }
ll modinv(ll a) { ll b = mod, u = 1, v = 0; while (b) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); }u %= mod; if (u < 0) u += mod; return u; }

int main(void) {
	int n, k;
	cin >> n >> k;
	vector<vector<int>> a(n, vector<int>(n));
	int r = 0, l = 0;
	rep(i, 0, n)rep(j, 0, n)cin >> a[i][j], r = max(r, a[i][j]);
	while (r - l > 1) {
		int m = (r + l) / 2;
		vector<vector<int>> s(n + 1, vector<int>(n + 1));
		rep(i, 0, n) {
			rep(j, 0, n) {
				if (a[i][j] > m)s[i + 1][j + 1] = 1;
				s[i + 1][j + 1] += s[i][j + 1] + s[i + 1][j] - s[i][j];
			}
		}
		bool ok = false;
		rep(x, 0, n - k + 1) {
			rep(y, 0, n - k + 1) {
				if (s[x + k][y + k] - s[x][y + k] - s[x + k][y] + s[x][y] <= k * k / 2) {
					ok = true;
					break;
				}
			}
			if (ok)break;
		}
		if (ok)r = m;
		else l = m;
	}
	printf("%d\n", r);
	return 0;
}
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define FORI(i,v) for (auto i = v.begin(); i != v.end(); i++)
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(ALL(v))
#define REV(v) reverse(ALL(v))
#define UNIQ(v) sort(ALL(v)); v.erase(unique(ALL(v)),end(v))
#define CHMIN(x,y) x = min(x, y)
#define CHMAX(x,y) x = max(x, y)
#define YES(b) cout << ((b) ? "YES" : "NO") << endl
#define Yes(b) cout << ((b) ? "Yes" : "No") << endl

const int MAX = 20;

int N, M;
vii X[MAX];
ll dp[1<<MAX];

int main() {
    cout << fixed << setprecision(15);
    cin >> N >> M;
    REP (i, M) {
        int x, y, z;
        cin >> x >> y >> z;
        X[x].push_back(make_pair(y, z));
    }

    vector<bool> visit(1<<N, false);
    queue<int> q;
    q.push(0);
    dp[0] = 1;
    while (q.size()) {
        int state = q.front(); q.pop();
        int b = __builtin_popcount(state) + 1;
        REP (i, N) if ((state & (1<<i)) == 0) {
            int next = state | (1<<i);
            bool check = true;
            FORE (x, X[b]) {
                if (__builtin_popcount(next&((1<<(x.first))-1)) > x.second) check = false;
            }
            if (check) {
                dp[next] += dp[state];
                if (!visit[next]) {
                    q.push(next);
                    visit[next] = true;
                }
            }
        }
    }
    cout << dp[(1<<N)-1] << endl;
}
