#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t = 1,n,m,k,q,l,r,a[809][809],b[809][809],c[809][809],u,v,x,y,z,mod = 1e9 + 7;
string s;
struct st{ll x,y; /*bool operator < (const st &a) const{return x < a.x;};*/};
bool cmp(const st &a,const st &b){return a.x < b.x;}
inline ll read(){
	ll s = 0,w = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
	return s * w;
}
ll qp(ll x,ll y){
	ll a = 1,b = x;
	while (y){
		if (y & 1) a = a * b % mod;
		b = b * b % mod,y >>= 1;
	}
	return a;
}
bool judge(ll x){
	for (ll i = 1;i <= n;i += 1) for (ll j = 1;j <= n;j += 1) c[i][j] = a[i][j] <= x;
	for (ll i = 1;i <= n;i += 1) for (ll j = 1;j <= n;j += 1) b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + c[i][j];
	for (ll i = 1;i <= n - k + 1;i += 1) for (ll j = 1;j <= n - k + 1;j += 1)
		if (b[i + k - 1][j + k - 1] - b[i - 1][j + k - 1] - b[i + k - 1][j - 1] + b[i - 1][j - 1] >= (k * k + 1) / 2){
			return 1;
		}
	return 0;
}
int main(){//t = read();
while (t --){
	n = read(),k = read();
	for (ll i = 1;i <= n;i += 1) for (ll j = 1;j <= n;j += 1) a[i][j] = read();
	ll l = 0,r = 1e9,ans = 1e9;
	while (l <= r){
		ll mid = (l + r) >> 1;
		if (judge(mid)) r = mid - 1,ans = mid;
		else l = mid + 1;
	}
	cout<<ans;
}
	return 0;
}
// Author:   old_school
// Created:  20.02.2021 17:30:29

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma") 
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define lld               long long int
#define ld                long double
#define pb                push_back
#define ppb               pop_back 
#define mp                make_pair
#define F                 first
#define S                 second
#define nl                '\n'
#define all(c)            (c).begin(),(c).end()
#define rall(c)           (c).rbegin(),(c).rend()
#define sz(c)             (c).size()
#define tr(x,a)           for(auto &a : x)
#define psnt(x,a)         (x).find(a)!=(x).end()
#define vpsnt(x,a)        find(all(x),a)!=(x).end()
#define MOD               1000000007
#define tod               100005
#define pi                3.1415926536
#define itr(i,a,b)        for(lld i=a;i<=b;i++)
#define itrn(i,a,b)       for(lld i=a;i>=b;i--)
#define iot(n)            for(lld i=0;i<n;i++)
#define pls(n,arr)        lld arr[n]; iot(n)  cin>>arr[i];
#define bye               fflush(stdout)

typedef pair<lld,lld>     pii;
typedef pair<string,lld>  psi;

template <typename T>
bool mycomp(T x,T y){ 
   return (x==y);  //give your condition here
}
bool paircomp(const pair<lld,lld> &x,const pair<lld,lld> &y){ 
return x.second<y.second;
}
vector<pair<lld,pair<lld,lld> > > adj[tod];
void dijkstra(lld V,lld source,lld dist[]){
    priority_queue<pair<lld,lld> ,vector<pair<lld,lld> >,greater<pair<lld,lld> > > pq; //minheap
    for(lld i=0;i<=V;i++)
       dist[i]=-1;
    dist[source]=0;
    pq.push(make_pair(dist[source],source));
    while(!pq.empty()){
        lld u=pq.top().second;
        pq.pop();
        for(auto &p:adj[u]){
            lld v=p.first,weight=p.second.first,lx=p.second.second;
            lld z=dist[u]/lx;
               lld ex=0;
               if(dist[u]%lx){
               	 z++;
               }
               z*=lx;
               ex=z-dist[u];   
            if (dist[v]==-1) 
            {   
                dist[v] = dist[u] + ex+weight; 
                pq.push(make_pair(dist[v], v)); 

            }
            else if(dist[v]>dist[u]+ex+weight){
                dist[v]=dist[u]+ex+weight;
                pq.push(make_pair(dist[v], v));   
            }
        }
    }
}
void solve(){
   lld n,m,x,y; cin>>n>>m>>x>>y;
   iot(m){
   	lld a,b,t,k; cin>>a>>b>>t>>k;
   	adj[a].pb({b,{t,k}});
   	adj[b].pb({a,{t,k}});
   }
   lld dist[n+1];
   dijkstra(n,x,dist);
   cout<<dist[y];
}
int main(){
       ios_base::sync_with_stdio(false);
             cin.tie(0);
            cout.tie(0);
      lld t=1;// cin>>t;  
      while(t--){
            solve();
            cout<<endl;
      }
}

