#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
using pii = pair<int, int>;

bool nBase(string s, ll n, ll m){
    __int128 res = 0;
    int len = s.length();
    for (int i = 0; i < len;i++){
        res = res * n + s[i] - '0';
        if(res > m)
            return false;
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string x;
    cin >> x;
    ll m;
    cin >> m;

    if(x.length()==1){
        cout << (atoi(x.c_str()) <= m ? 1 : 0);
        return 0;
    }

    int d = *max_element(x.begin(), x.end()) - '0';
    ll l = d + 1, r = 1e18;
    while(l <= r){
        ll mid = (l + r) / 2;
        if(nBase(x, mid, m)){
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    cout << max(0ll, l - d - 1) << '\n';
    return 0;
}


//                        YATIN KWATRA

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll                      long long
#define ar                      array
#define sz(v)                   (int)(v.size())
#define inf                     1e18
#define int                     ll
#define FIO                     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ld                      long double
#define ull                     unsigned long long
#define endl                    "\n"
#define fo(i,a,b)               for(int i = a; i<=b ; i++)
#define rfo(i,a,b)              for(int i = a; i>=b ; i--)
#define vii                     vector<int>
#define pq                      priority_queue
#define uomii                   unordered_map<int,int,best_hash>
#define all(v)                  v.begin(),v.end()
#define mp                      make_pair
#define pb                      push_back
#define pob                     pop_back
#define ff                      first
#define ss                      second
#define pii                     pair<int,int>
#define mii                     map<int,int>
#define vvii                    vector<vii>
#define mod                     1000000007
#define MIN                     -1e9
#define pi                      3.1415926535897932384626433832795
#define cz(x)                   63 - __builtin_clzll(x)

using namespace std;
using namespace __gnu_pbds;
template<class T> using oset =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


struct best_hash {
	static uint64_t splitmix64(uint64_t x) {

		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

void INPUT()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

/*
----------------------------------------------------------------
   -> Check For Overflows
   -> Out of Bounds
   -> Initialisations of global arrays and variables
----------------------------------------------------------------
*/

const int N = 805;
int v[N][N];
int a[N][N];
int dp[N][N];
int n, k;

bool possible(int med) {
	// so we can do like this in order to check if there is any matrix of size
	// K * K, such that median is  <= med.
	// we can convert all values greater than med into 1 and other to 0
	// so if sum of a k * k matrix is <= (k*k)/2 , so median can be <= med

	fo(i, 0, n - 1) {
		fo(j, 0, n - 1) {
			if (v[i][j] > med) a[i][j] = 1;
			else a[i][j] = 0;
		}
	}

	dp[0][0] = a[0][0];

	fo(i, 1, n - 1) {
		dp[0][i] = dp[0][i - 1] + a[0][i];
		dp[i][0] = dp[i - 1][0] + a[i][0];
	}

	fo(i, 1, n - 1) {
		int sum = a[i][0];
		fo(j, 1, n - 1) {
			dp[i][j] = dp[i - 1][j] + a[i][j] + sum;
			sum += a[i][j];
		}
	}

	fo(i, k - 1, n - 1) {
		fo(j, k - 1, n - 1) {
			int sum = dp[i][j];
			if ((j - k) >= 0) sum -= dp[i][j - k];
			if ((i - k) >= 0) sum -= dp[i - k][j];
			if ((i - k) >= 0 and (j - k) >= 0) sum += dp[i - k][j - k];
			if (sum <= ((k * k) / 2)) return 1;
		}
	}
	return 0;
}

void solve()
{
	cin >> n >> k;
	fo(i, 0, n - 1) {
		fo(j, 0, n - 1) cin >> v[i][j];
	}
	int low = 0, high = 1e9, ans = 1e9, mid;
	while (low <= high) {
		mid = (low + high) / 2;
		if (possible(mid)) {
			ans = mid;
			high = mid - 1;
		}
		else low = mid + 1;
	}
	cout << ans;
}

signed main() {

	FIO
	INPUT();

	int t;
	t = 1;
	//cin >> t;
	fo(i, 0, t - 1) {
		solve();
	}
	return 0;
}
