#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline)) static
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
using ll = long long;

#define IC isdigit(c)
#define GC c=getchar()
void rd(auto &x) { x = 0; char GC; bool f = 0;
	for (; !IC; GC) f |= c == '-';
	for (; IC; GC) x = x * 10 + c - 48;
	if (f) x = -x;
}
void rd(auto &x, auto &...y) { rd(x); rd(y...); }
#define meow(...) fprintf(stderr, __VA_ARGS__)
#define Assert(e, v) if (!(e)) { meow("AF@%d\n", __LINE__ ); exit(v); }

#define vc vector
#define eb emplace_back
#define pb push_back

const int N = 250005;
ll k;

#define mid ((l + r) >> 1)
#define ls (p << 1)
#define rs (ls | 1)
#define arg int p, ll l, ll r
#define L ls, l, mid
#define R rs, mid + 1, r
struct node {
	ll mx, tag;
	void apply(ll v) { mx += v; tag += v; }
} tr[N * 16];
void add(int b, int e, ll v, arg) {
	if (b <= l && e >= r) {
		tr[p].apply(v);
		return;
	}
	if (b <= mid) add(b, e, v, L);
	if (e > mid) add(b, e, v, R);
	tr[p].mx = max(tr[ls].mx, tr[rs].mx) + tr[p].tag;
}
ll query(int b, int e, arg) {
	if (b <= l && e >= r) return tr[p].mx;
	ll v = -1;
	if (b <= mid) v = query(b, e, L);
	if (e > mid) v = max(v, query(b, e, R));
	assert(v >= 0);
	return v + tr[p].tag;
}
const int rt = 1;
ll lsh[N * 2]; int KI;
void add(int b, int e, ll v) {
	b = lower_bound(lsh + 1, lsh + KI + 1, b) - lsh;
	e = lower_bound(lsh + 1, lsh + KI + 1, e) - lsh;
	if (b <= e)
		add(b, e, v, rt, 1, KI);
	else
		add(b, KI, v, rt, 1, KI),
		add(1, e, v, rt, 1, KI);
}
ll query(int b, int e) {
	b = lower_bound(lsh + 1, lsh + KI + 1, b) - lsh;
	e = lower_bound(lsh + 1, lsh + KI + 1, e) - lsh;
	if (b <= e)
		return query(b, e, rt, 1, KI);
	else
		return max(
			query(b, KI, rt, 1, KI),
			query(1, e, rt, 1, KI)
		);
}
void check(int x, ll v) {
	ll w = query(x, x);
	if (v > w)
		add(x, x, v - w);
}
ll M(ll x) { return (((x) % k + k) % k); }

//void test() {
//	k = 5;
//	add(1, 1, 2);
//	ll t = query(1, 1);
//	cout << t << endl;
//	exit(0);
//}

ll play_game(ll m, int n, ll _k, vc<ll> lp, vc<ll> rp) {
	clog << "#" << sizeof(tr) / 1048576 << endl;
//	test();
	
	k = _k;
	map<ll, int> di;
	di[0] = 0;
	U (i, 0, n - 1) {
		ll l = lp[i], r = rp[i];
		++di[l]; --di[r + 1];
	}
	di[m + ll(1e18)] = 0;
	ll a = 0;
	
	lsh[1] = 0; lsh[2] = k - 1; KI = 2;
	for (auto [x, y] : di) {
		lsh[++KI] = M(x);
		lsh[++KI] = M(x - 1);
	}
	sort(lsh + 1, lsh + KI + 1);
	KI = unique(lsh + 1, lsh + KI + 1) - lsh - 1;
	
	for (auto it = di.begin(), jt = next(it); jt != di.end(); it = jt, ++jt) {
		ll i = it->first, j = jt->first; ll d = it->second;
		ll mi = i % k, mj = j % k;
		a += d;
		
		ll w = query(mi, M(mj - 1)) + ((j - i) / k) * a;
		if (mi != mj)		
			add(mi, M(mj - 1), ((j - i) / k + 1) * a);
		add(mj, M(mi - 1), ((j - i) / k) * a);
		check(mj, w);
	}
	
	ll ans = tr[1].mx;
	return ans;
}