// -- //
#include <bits/stdc++.h>
#define pll pair<ll, ll>
#define x first
#define y second
using namespace std;
typedef long long ll;
const ll N = 808;
ll a[N][N];
ll p[N][N];
signed main(){
	cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
    ll n, k;cin >> n>>k;
    for(ll i = 0;i<n;i++){
        for(ll j = 0;j<n;j++){
            cin >> a[i][j];
        }
    }
    ll l = -1, r=1e9; //(l;r]
    while(r-l>1){
        ll m = (l+r)>>1;
        bool ok =0;
        for(ll i = 0;i<n&&!ok;i++){
            for(ll j = 0;j<n&&!ok;j++){
                p[i][j] = (a[i][j]>m?-1:1);
                if(i) p[i][j]+=p[i-1][j];
                if(j) p[i][j]+=p[i][j-1];
                if(i&&j) p[i][j]-=p[i-1][j-1];
                if(i>=k-1&&j>=k-1){
                    ll e = p[i][j];
                    if(i-k>=0) e-=p[i-k][j];
                    if(j-k>=0) e-=p[i][j-k];
                    if(i-k>=0&&j-k>=0) e+=p[i-k][j-k];
                    if(e>=0) ok=1;
                }
            }
        }
        // ok=1 if exists square with median <= m
        if(ok) r=m;
        else l=m;
    }
    cout<<r;
}

#include <bits/stdc++.h>

#define speedup ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr),cout.precision(12)
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_map;
#define sbc __builtin_popcount
#define pb push_back
#define pbk pop_back
#define em emplace
#define emb emplace_back
#define ff first
#define ss second
#define ll long long
const ll mod = 1e9 + 7;

template<typename T> void smax(T& a, T b) { if(a<b) a=b; }
template<typename T> void smin(T& a, T b) { if(a>b) a=b; }
template<typename T> T pw(T a,T b) { T p=1,one=1; while(b) { if(b&one) p=p*a; a=a*a; b >>=1; } return p; }
template<typename T> T pwm(T a,T b,T md=mod) { T p=1,one=1; while(b) { if(b&one) p=p*a%md; a=a*a%md; b >>=1; } return p; }

template<typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (auto &it:v)
        is >> it;
    return is;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &it) {
    os << it.first << ' ' << it.second;
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const array<T, 2> &v) {
    for (auto &it : v) os << it << ' ';
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for (auto &it : v)
        os << it << ' ';
    return os;
}

#ifndef ONLINE_JUDGE
class Timer { chrono::high_resolution_clock::time_point start_t, end_t; public: Timer() { start_t=chrono::high_resolution_clock::now(); } ~Timer() { end_t = chrono::high_resolution_clock::now(); auto duration = chrono::duration_cast<chrono::milliseconds>(end_t-start_t); cerr<<"\nRunTime: "<<duration.count()<<"ms"<<'\n'; } };
void debug() { cerr << '\n'; }

template<typename T, typename... Args>
void debug(T print, Args... args) {
    cerr << ' ' << print;
    debug(args...);
}

#define deb(...) cerr << "[" << #__VA_ARGS__ << "]" << " --> ", debug(__VA_ARGS__)
#else
#define deb(...) void(0)
#endif
void solve() {	
	int n;
	int64_t c;
	cin>>n>>c;
	map<int,pair<int64_t,int64_t>> mp;
	for(int i=0,x,y,z;i<n;++i) {
		cin>>x>>y>>z;
		mp[x].ff+=z;
		mp[y].ss+=z;
	}
	int64_t ans=0;
	int p=mp.begin()->ff-1;
	int64_t s=0;
	for(auto& it:mp) {
		int pos=it.ff;
		int64_t add=it.ss.ff, sub=it.ss.ss;

		if(pos-p>1)
			ans+=min(s,c)*(pos-p-1);	
		
		s+=add;
		ans+=min(s,c);
		
		s-=sub;

		p=pos;
	}
	cout<<ans<<'\n';
}
int main() {
    speedup;
    //int t; cin >> t; while (t--)
	solve();
}
/**Vim
 *
 *
 *
 *
 *
 *
 *
 *
 */
