#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <limits>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif
using ll = long long;
using vll = std::vector<ll>;
using vvll = std::vector<vll>;
using vvvll = std::vector<vvll>;
#define reps(i, S, E) for (ll i = (S); i <= (E); i++)
#define rep(i, N) reps(i, 0, N-1)
#define deps(i, E, S) for (ll i = (E); i >= (S); i--)
#define dep(i, N) deps(i, N-1, 0)
const ll INF = 1LL << 60;
const int INF_INT = 1 << 30;

template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; }return false; }
struct mll {
	static ll MOD;
	ll val;
	mll(ll v = 0) : val(v % MOD) { if (val < 0) val += MOD; }
	mll operator - () const { return -val; }
	mll operator + (const mll &b) const { return val + b.val; }
	mll operator - (const mll &b) const { return val - b.val; }
	mll operator * (const mll &b) const { return val * b.val; }
	mll operator / (const mll &b) const { return mll(*this) /= b; }
	mll operator + (ll b) const { return *this + mll(b); }
	mll operator - (ll b) const { return *this - mll(b); }
	mll operator * (ll b) const { return *this * mll(b); }
	friend mll operator + (ll a, const mll &b) { return b + a; }
	friend mll operator - (ll a, const mll &b) { return -b + a; }
	friend mll operator * (ll a, const mll &b) { return b * a; }
	mll &operator += (const mll &b) { val = (val + b.val) % MOD; return *this; }
	mll &operator -= (const mll &b) { val = (val + MOD - b.val) % MOD; return *this; }
	mll &operator *= (const mll &b) { val = (val*b.val) % MOD; return *this; }
	mll &operator /= (const mll &b) {
		ll c = b.val, d = MOD, u = 1, v = 0;
		while (d) {
			ll t = c / d;
			c -= t * d; swap(c, d);
			u -= t * v; swap(u, v);
		}
		val = val * u % MOD;
		if (val < 0) val += MOD;
		return *this;
	}
	mll &operator += (ll b) { return *this += mll(b); }
	mll &operator -= (ll b) { return *this -= mll(b); }
	mll &operator *= (ll b) { return *this *= mll(b); }
	mll &operator /= (ll b) { return *this /= mll(b); }
	bool operator == (const mll &b) { return val == b.val; }
	bool operator != (const mll &b) { return val != b.val; }
	bool operator == (ll b) { return *this == mll(b); }
	bool operator != (ll b) { return *this != mll(b); }
	friend bool operator == (ll a, const mll &b) { return mll(a) == b.val; }
	friend bool operator != (ll a, const mll &b) { return mll(a) != b.val; }
	friend ostream &operator << (ostream &os, const mll &a) { return os << a.val; }
	friend istream &operator >> (istream &is, mll &a) { return is >> a.val; }
	static mll Combination(ll a, ll b) {
		chmin(b, a - b);
		if (b < 0) return mll(0);
		mll c = 1;
		rep(i, b) c *= a - i;
		rep(i, b) c /= i + 1;
		return c;
	}
};
using vmll = std::vector<mll>;
using vvmll = std::vector<vmll>;
using vvvmll = std::vector<vvmll>;
using vvvvmll = std::vector<vvvmll>;

//struct Fast {
//	Fast() {
//		cin.tie(0);
//		ios::sync_with_stdio(false);
//		cout << fixed << setprecision(std::numeric_limits<double>::max_digits10);
//	}
//} fast; //cin,cout高速化のおまじない＋桁数指定
//
//ll mll::MOD = (ll)(1e9 + 7);// 998244353ll;


//AtCoder Grand Contest 038 - B
template< typename Monoid >
struct SegmentTree {
	using F = function< Monoid(Monoid, Monoid) >;

	int sz;
	vector< Monoid > seg;

	const F f;
	const Monoid M1;

	SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
		sz = 1;
		while (sz < n) sz <<= 1;
		seg.assign(2 * sz, M1);
	}

	void set(int k, const Monoid &x) {
		seg[k + sz] = x;
	}

	void build() {
		for (int k = sz - 1; k > 0; k--) {
			seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
		}
	}

	void update(int k, const Monoid &x) {
		k += sz;
		seg[k] = x;
		while (k >>= 1) {
			seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
		}
	}

	Monoid query(int a, int b) {
		Monoid L = M1, R = M1;
		for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
			if (a & 1) L = f(L, seg[a++]);
			if (b & 1) R = f(seg[--b], R);
		}
		return f(L, R);
	}

	Monoid operator[](const int &k) const {
		return seg[k + sz];
	}

	template< typename C >
	int find_subtree(int a, const C &check, Monoid &M, bool type) {
		while (a < sz) {
			Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
			if (check(nxt)) a = 2 * a + type;
			else M = nxt, a = 2 * a + 1 - type;
		}
		return a - sz;
	}


	template< typename C >
	int find_first(int a, const C &check) {
		Monoid L = M1;
		if (a <= 0) {
			if (check(f(L, seg[1]))) return find_subtree(1, check, L, false);
			return -1;
		}
		int b = sz;
		for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
			if (a & 1) {
				Monoid nxt = f(L, seg[a]);
				if (check(nxt)) return find_subtree(a, check, L, false);
				L = nxt;
				++a;
			}
		}
		return -1;
	}

	template< typename C >
	int find_last(int b, const C &check) {
		Monoid R = M1;
		if (b >= sz) {
			if (check(f(seg[1], R))) return find_subtree(1, check, R, true);
			return -1;
		}
		int a = sz;
		for (b += sz; a < b; a >>= 1, b >>= 1) {
			if (b & 1) {
				Monoid nxt = f(seg[--b], R);
				if (check(nxt)) return find_subtree(b, check, R, true);
				R = nxt;
			}
		}
		return -1;
	}
};

//SegmentTree(n, f, M1):= サイズ n の初期化。ここで f は2つの区間の要素をマージする二項演算, M1 はモノイドの単位元である。
//set(k, x):= k 番目の要素に x を代入する。
//build():= セグメント木を構築する。
//query(a, b):= 区間 [a,b) に対して二項演算した結果を返す。
//update(k, x):= k 番目の要素を x に変更する。
//operator[k] := k 番目の要素を返す。
//find_first(a, check) := [a,x) が check を満たす最初の要素位置 x を返す。
//find_last(b, check) := [x,b) が check を満たす最後の要素位置 x を返す。

//使用例
//int main() {
//	int N, Q;
//	scanf("%d %d", &N, &Q);
//	SegmentTree< int > seg(N, [](int a, int b) { return min(a, b); }, INF_INT);
//	while(Q--) {
//		int T, X, Y;
//		scanf("%d %d %d", &T, &X, &Y);
//		if(T == 0) seg.update(X, Y);
//		else printf("%d\n", seg.query(X, Y + 1));
//	}
//}

int main() {
	int N;
	cin >> N;
	int K;
	cin >> K;

	vector<int> P(N);
	SegmentTree<int> segMin(N, [](int a, int b) { return min(a, b); }, INF_INT);
	SegmentTree<int> segMax(N, [](int a, int b) { return max(a, b); }, -1);

	rep(i, N) {
		cin >> P[i];
		segMin.update(i, P[i]);
		segMax.update(i, P[i]);
	}

	vll totalUp(N, 0);
	totalUp[0] = 1;
	rep(i, N - 1) {
		totalUp[i + 1] = totalUp[i];
		if (P[i] < P[i + 1]) {
			totalUp[i + 1]++;
		}
	}

	bool noChange = false;
	int result = 1; //1つめは必ずカウント
	if (totalUp[K - 1] == K) {
		noChange = true;
		eprintf("noChange\n");
	}

	reps(i, 0, N - K - 1) {
		bool change = false;
		int seg_min = segMin.query(i + 1, i + K);
		int seg_max = segMax.query(i + 1, i + K);

		eprintf("P[%lld]=%d %d - %d P[%lld]=%d\n", i, P[i], seg_min, seg_max, i+K, P[i + K]);

		//P[i]を抜いて変化があるか？
		if (P[i] > seg_min) {
			change = true;
		}

		//ノーチェンジではないか？
		if (change == true) {
			if (totalUp[i + K] - totalUp[i + 1] == K - 1) {
				if (noChange == true) {
					//ノーチェンジダブルカウント防止
					change = false;
					eprintf("noChange\n");
				}
				else {
					noChange = true;
					eprintf("noChange\n");
				}
			}
		}

		if (change == false) {
			//P[i + K]を入れて変化があるか？
			if (P[i + K] < seg_max) {
				change = true;
			}
		}

		if (change == true) {
			result++;
		}
	}

	cout << result << endl;

	return 0;
}



//AtCoder Beginner Contest 108 - D
/*
ll LLpow(ll x, ll n) {
	ll ret = 1;
	while (n > 0) {
		if (n & 1) {
			ret *= x;
		}
		x *= x;
		n >>= 1;
	}
	return ret;
}

int main() {
	ll L;
	cin >> L;

	vll keta(13);
	ll maxKeta = 0;
	rep(i, 13) {
		keta[i] = L % 3;
		L /= 3;
		if (keta[i] > 0) {
			maxKeta = i;
		}
	}

	ll nodeNum = maxKeta + 2; //maxKeta+1のノード間が必要
	vll eFrom;
	vll eTo;
	vll eWeight;

	//base
	rep(i, maxKeta) {
		rep(j, 3) {
			eFrom.push_back(nodeNum - i - 1);
			eTo.push_back(nodeNum - i);
			eWeight.push_back(LLpow(3, i) * j);
		}
	}
	rep(i, keta[maxKeta]) {
		eFrom.push_back(1);
		eTo.push_back(2);
		eWeight.push_back(LLpow(3, maxKeta) * i);
	}

	//skip
	ll nextNum = LLpow(3, maxKeta) * keta[maxKeta];
	deps(i, maxKeta - 1, 0) {
		rep(j, keta[i]) {
			eFrom.push_back(1);
			eTo.push_back(nodeNum - i);
			eWeight.push_back(nextNum);
			nextNum += LLpow(3, i);
		}
	}

	//output
	cout << nodeNum << " " << eFrom.size() << endl;
	rep(i, eFrom.size()) {
		cout << eFrom[i] << " " << eTo[i] << " " << eWeight[i] << endl;
	}

	return 0;
}
*/

//AtCoder Beginner Contest 110 - D
/*
void DecompositPrime(ll n, map<ll, ll> &result) {
	result.clear();
	ll a = 2;
	while (n >= a * a) {
		if (n % a == 0) {
			result[a]++;
			n /= a;
		}
		else {
			a++;
		}
	}
	if (n > 1) {
		result[n]++;
	}
}

int main() {
	ll N;
	cin >> N;
	ll M;
	cin >> M;

	//if (M == 1) {
	//	cout << 1 << endl;
	//	return 0;
	//}

	map<ll, ll> mp;
	DecompositPrime(M, mp);

	mll result = 1;

	auto begin = mp.begin(), end = mp.end();
	for (auto iter = begin; iter != end; iter++) {
		// iter->first: key, iter->second: value
		result *= mll::Combination(iter->second + N - 1, N - 1);
	}

	cout << result << endl;

	return 0;
}
*/

//AtCoder Grand Contest 018 - B
/*
int main() {
	ll N;
	cin >> N;
	ll M;
	cin >> M;
	vvll A(N, vll(M));
	rep(i, N) rep(j, M) {
		cin >> A[i][j];
		A[i][j]--; //0 origin
	}

	ll result = INF;
	vector<bool> unselected(M, false);
	vll mIndex(N, 0);

	rep(j, M) {
		//現在の状況での参加分布を調査
		vll count(M, 0);

		rep(i, N) {
			count[A[i][mIndex[i]]]++;
			eprintf("%lld: [%lld] %lld\n", i, mIndex[i], A[i][mIndex[i]]);
		}

		ll maxCount = 0;
		ll maxM = -1;
		rep(i, M) {
			if (chmax(maxCount, count[i]) == true) {
				maxM = i;
			}
			eprintf("count[%lld]: %lld\n", i, count[i]);
		}
		eprintf("unselect: %d\n", maxM);

		chmin(result, maxCount);

		//maxMの競技行わないようにして次の調査へ
		unselected[maxM] = true;
		rep(i, N) {
			while (mIndex[i] < M && unselected[A[i][mIndex[i]]] == true) {
				mIndex[i]++;
			}
		}
	}

	cout << result << endl;

	return 0;
}
*/

//AtCoder Beginner Contest 057 - D
/*
ll comb(ll n, ll r) {
	ll num = 1;
	for (ll i = 1; i <= r; i++) {
		num = num * (n - i + 1) / i;
	}
	return num;
}

int main() {
	ll N;
	cin >> N;
	ll A;
	cin >> A;
	ll B;
	cin >> B;
	vector<ll> v(N);
	rep(i, N) {
		cin >> v[i];
	}

	std::sort(v.begin(), v.end());

	double result1 = 0;
	ll maxSum = 0;
	deps(i, N - 1, N - A) {
		maxSum += v[i];
	}
	result1 += (double)maxSum / (double)A;

	cout << result1 << endl;

	ll result2 = 0;

	reps(i, A, B) {
		if (i > A && v[N - i] < v[N - 1]) {
			continue;
		}

		ll boundary = v[N - i];
		ll lowerIndex = lower_bound(v.begin(), v.end(), boundary) - v.begin();
		ll upperIndex = upper_bound(v.begin(), v.end(), boundary) - v.begin();
		ll c = comb(upperIndex - lowerIndex, upperIndex - (N - i));
		result2 += c;
	}

	cout << result2 << endl;

	return 0;
}
*/

//AtCoder Beginner Contest 054 - D
/*
int main() {
	ll N;
	cin >> N;
	ll Ma;
	cin >> Ma;
	ll Mb;
	cin >> Mb;
	vll a(N);
	vll b(N);
	vll c(N);
	rep(i, N) {
		cin >> a[i] >> b[i] >> c[i];
	}

	vvvll dp(N + 1, vvll(400 + 1, vll(400 + 1, INF)));
	dp[0][0][0] = 0;

	rep(i, N) rep(j, 400 + 1) rep(k, 400 + 1) {
		if (dp[i][j][k] == INF) {
			continue;
		}

		//buy
		chmin(dp[i + 1][j + a[i]][k + b[i]], dp[i][j][k] + c[i]);

		//not buy
		chmin(dp[i + 1][j][k], dp[i][j][k]);
	}

	//rep(j, 6 + 1) {
	//	rep(k, 6 + 1) {
	//		eprintf("%lld ", dp[N][j][k] == INF ? -1 : dp[N][j][k]);
	//	}
	//	eprintf("\n");
	//}

	ll result = INF;

	rep(j, 400 + 1) rep(k, 400 + 1) {
		if (dp[N][j][k] == INF) {
			continue;
		}

		if (j == 0 || k == 0) {
			continue;
		}

		if (j * Mb == k * Ma) {
			chmin(result, dp[N][j][k]);
		}
	}

	if (result == INF) {
		cout << -1 << endl;
	}
	else {
		cout << result << endl;
	}

	return 0;
}
*/


//AtCoder Beginner Contest 104 - D
/*
int main() {
	string s;
	cin >> s;
	ll len_s = s.size();

	vvmll dp(len_s + 1, vmll(4, 0));
	dp[0][0] = 1;

	rep(i, len_s) {
		//not get
		dp[i + 1][0] += dp[i][0];
		dp[i + 1][1] += dp[i][1];
		dp[i + 1][2] += dp[i][2];
		dp[i + 1][3] += dp[i][3];

		switch (s[i])
		{
		case 'A':
			dp[i + 1][1] += dp[i][0];
			break;
		case 'B':
			dp[i + 1][2] += dp[i][1];
			break;
		case 'C':
			dp[i + 1][3] += dp[i][2];
			break;
		case '?':
			//A
			dp[i + 1][1] += dp[i][0];

			//B
			dp[i + 1][2] += dp[i][1];

			//C
			dp[i + 1][3] += dp[i][2];

			//not get
			dp[i + 1][0] += dp[i][0];
			dp[i + 1][1] += dp[i][1];
			dp[i + 1][2] += dp[i][2];
			dp[i + 1][3] += dp[i][3];

			//not get
			dp[i + 1][0] += dp[i][0];
			dp[i + 1][1] += dp[i][1];
			dp[i + 1][2] += dp[i][2];
			dp[i + 1][3] += dp[i][3];
			break;
		default:
			break;
		}
	}

	rep(i, len_s + 1) {
		rep(j, 4) {
			eprintf("%lld ", dp[i][j].val);
		}
		eprintf("\n");
	}

	ll result = dp[len_s][3].val;

	cout << result << endl;

	return 0;
}
*/

//AtCoder Beginner Contest 147 - E
/*
int main() {
	ll H;
	cin >> H;
	ll W;
	cin >> W;
	vvll A(H, vll(W));
	rep(i, H) rep(j, W) {
		cin >> A[i][j];
	}
	vvll B(H, vll(W));
	rep(i, H) rep(j, W) {
		cin >> B[i][j];
	}

	vvll C(H, vll(W));
	rep(i, H) rep(j, W) {
		C[i][j] = abs(A[i][j] - B[i][j]);
	}

	ll MAX_SUB = 12800;
	vector<vector<vector<bool>>> dp(H, vector<vector<bool>>(W, vector<bool>(MAX_SUB * 2, false)));

	// -12800すると元の偏りの数値に
	dp[0][0][MAX_SUB + C[0][0]] = true;
	dp[0][0][MAX_SUB - C[0][0]] = true;

	rep(j, H) {
		rep(i, W) {
			rep(k, MAX_SUB * 2) {
				if (dp[j][i][k] == true) {
					if (i < W - 1) {
						//右へ
						dp[j][i + 1][k - C[j][i + 1]] = true;
						dp[j][i + 1][k + C[j][i + 1]] = true;
					}

					if (j < H - 1) {
						//下へ
						dp[j + 1][i][k - C[j + 1][i]] = true;
						dp[j + 1][i][k + C[j + 1][i]] = true;
					}
				}
			}
		}
	}

	ll result = INF;

	rep(k, MAX_SUB * 2) {
		if (dp[H - 1][W - 1][k] == true) {
			chmin(result, abs(k - MAX_SUB));
		}
	}

	cout << result << endl;

	return 0;
}
*/

//AtCoder Grand Contest 040 - B
/*
template< typename Monoid >
struct SegmentTree {
	using F = function< Monoid(Monoid, Monoid) >;

	int sz;
	vector< Monoid > seg;

	const F f;
	const Monoid M1;

	SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
		sz = 1;
		while (sz < n) sz <<= 1;
		seg.assign(2 * sz, M1);
	}

	void set(int k, const Monoid &x) {
		seg[k + sz] = x;
	}

	void build() {
		for (int k = sz - 1; k > 0; k--) {
			seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
		}
	}

	void update(int k, const Monoid &x) {
		k += sz;
		seg[k] = x;
		while (k >>= 1) {
			seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
		}
	}

	Monoid query(int a, int b) {
		Monoid L = M1, R = M1;
		for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
			if (a & 1) L = f(L, seg[a++]);
			if (b & 1) R = f(seg[--b], R);
		}
		return f(L, R);
	}

	Monoid operator[](const int &k) const {
		return seg[k + sz];
	}

	template< typename C >
	int find_subtree(int a, const C &check, Monoid &M, bool type) {
		while (a < sz) {
			Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
			if (check(nxt)) a = 2 * a + type;
			else M = nxt, a = 2 * a + 1 - type;
		}
		return a - sz;
	}

	template< typename C >
	int find_first(int a, const C &check) {
		Monoid L = M1;
		if (a <= 0) {
			if (check(f(L, seg[1]))) return find_subtree(1, check, L, false);
			return -1;
		}
		int b = sz;
		for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
			if (a & 1) {
				Monoid nxt = f(L, seg[a]);
				if (check(nxt)) return find_subtree(a, check, L, false);
				L = nxt;
				++a;
			}
		}
		return -1;
	}

	template< typename C >
	int find_last(int b, const C &check) {
		Monoid R = M1;
		if (b >= sz) {
			if (check(f(seg[1], R))) return find_subtree(1, check, R, true);
			return -1;
		}
		int a = sz;
		for (b += sz; a < b; a >>= 1, b >>= 1) {
			if (b & 1) {
				Monoid nxt = f(seg[--b], R);
				if (check(nxt)) return find_subtree(b, check, R, true);
				R = nxt;
			}
		}
		return -1;
	}
};

//SegmentTree(n, f, M1):= サイズ n の初期化。ここで f は2つの区間の要素をマージする二項演算, M1 はモノイドの単位元である。
//set(k, x):= k 番目の要素に x を代入する。
//build():= セグメント木を構築する。
//query(a, b):= 区間 [a,b) に対して二項演算した結果を返す。
//update(k, x):= k 番目の要素を x に変更する。
//operator[k] := k 番目の要素を返す。
//find_first(a, check) := [a,x) が check を満たす最初の要素位置 x を返す。
//find_last(b, check) := [x,b) が check を満たす最後の要素位置 x を返す。

//使用例
//int main() {
//	int N, Q;
//	scanf("%d %d", &N, &Q);
//	SegmentTree< int > seg(N, [](int a, int b) { return min(a, b); }, INT_MAX);
//	while(Q--) {
//		int T, X, Y;
//		scanf("%d %d %d", &T, &X, &Y);
//		if(T == 0) seg.update(X, Y);
//		else printf("%d\n", seg.query(X, Y + 1));
//	}
//}

struct LLPair {
	int a = 0;
	int b = 0;
	LLPair() {}
	LLPair(int a, int b) {
		this->a = a;
		this->b = b;
	}
};

int main() {
	int N;
	scanf("%d", &N);
	vector<LLPair> P(N);
	rep(i, N) {
		int l;
		scanf("%d", &l);
		int r;
		scanf("%d", &r);
		P[i].a = l;
		P[i].b = r;
	}

	std::sort(P.begin(), P.end(), [](const LLPair &a, const LLPair &b) {
		return a.a < b.a; //降順にするには > とする
	});

	SegmentTree<int> segMin(N, [](int a, int b) { return min(a, b); }, INF_INT);
	rep(i, N) {
		segMin.update(i, P[i].b);
	}

	int result = 0;

	rep(i, N - 1) {
		//iをグループ1とする
		//i+1～N-1までをグループ2とする
		//0～i-1をグループ1か2に割り当てる

		int g1l = P[i].a;
		int g2l = P[N - 1].a;

		if (i == 0) {
			int g1r = P[i].b;
			int g2r = segMin.query(i + 1, N);
			result = max(result, max(0, g1r - g1l + 1) + max(0, g2r - g2l + 1));
		}
		else {
			//0～i-1をグループ1に割り当てる
			{
				int g1r = min(P[i].b, segMin.query(0, i));
				int g2r = segMin.query(i + 1, N);
				result = max(result, max(0, g1r - g1l + 1) + max(0, g2r - g2l + 1));
			}

			//0～i-1をグループ2に割り当てる
			{
				int g1r = P[i].b;
				int g2r = min(segMin.query(0, i), segMin.query(i + 1, N));
				result = max(result, max(0, g1r - g1l + 1) + max(0, g2r - g2l + 1));
			}
		}
	}

	printf("%d\n", result);
}
*/

//AtCoder Beginner Contest 018 - D
/*
// nCkの組み合わせに対して処理を実行する
void recursive_comb(int *indexes, int s, int rest, std::function<void(int *)> f) {
	if (rest == 0) {
		f(indexes);
	}
	else {
		if (s < 0) return;
		recursive_comb(indexes, s - 1, rest, f);
		indexes[rest - 1] = s;
		recursive_comb(indexes, s - 1, rest - 1, f);
	}
}

void foreach_comb(int n, int k, std::function<void(int *)> f) {
	int *indexes = new int[k];
	recursive_comb(indexes, n - 1, k, f);
	delete[] indexes;
}

struct LLPair {
	ll a = 0;
	ll b = 0;
	LLPair() {}
	LLPair(ll a, ll b) {
		this->a = a;
		this->b = b;
	}
};

ll N;
ll M;
ll P;
ll Q;
ll R;
vll x;
vll y;
vll z;
ll choco[20][20];
ll result = 0;

int main() {
	scanf("%lld", &N);
	scanf("%lld", &M);
	scanf("%lld", &P);
	scanf("%lld", &Q);
	scanf("%lld", &R);
	x.resize(R);
	y.resize(R);
	z.resize(R);
	rep(i, R) {
		ll a;
		scanf("%lld", &a);
		ll b;
		scanf("%lld", &b);
		ll c;
		scanf("%lld", &c);
		x[i] = a - 1;
		y[i] = b - 1;
		z[i] = c;
	}

	memset(choco, 0, sizeof(choco));
	rep(i, R) {
		choco[x[i]][y[i]] = z[i];
	}

	//実行部
	foreach_comb(N, P, [](int *indexes) {
		//std::cout << indexes[0] << ',' << indexes[1] << ',' << indexes[2] << ',' << indexes[3] << ',' << indexes[4] << std::endl;
		vector<LLPair> men(M); //男子[i]が参加することによる幸福度
		rep(i, M) {
			men[i].a = i;
			men[i].b = 0;
		}

		rep(i, P) {
			rep(j, M) {
				men[j].b += choco[indexes[i]][j];
			}			
		}

		std::sort(men.begin(), men.end(), [](const LLPair &a, const LLPair &b) {
			return a.b > b.b; //降順にするには > とする
		});

		ll happy = 0;
		rep(i, Q) {
			happy += men[i].b;
		}

		result = max(result, happy);
	});

	printf("%lld\n", result);
}
*/

//AtCoder Regular Contest 088
/*
int main() {
	char S[101010];
	scanf("%s", S);
	ll len = strlen(S);

	vll cont;
	char prev = ' ';
	ll count = 0;
	rep(i, len) {
		if (S[i] != prev && i > 0) {
			cont.push_back(count);
			count = 1;
		}
		else {
			count++;
		}

		prev = S[i];
	}
	cont.push_back(count);

	ll result = 0;
	if (cont.size() == 1) {
		result = cont[0];
	}
	else {
		//result = max(result, cont[0]);
		//result = max(result, cont[cont.size() - 1]);
		//reps(i, 1, cont.size() - 2) {
		//	ll temp = min(cont[i - 1] + cont[i], cont[i] + cont[i + 1]);
		//	result = max(result, temp);
		//}

		vll sumLeft(cont.size(), 0);
		sumLeft[0] = cont[0];
		reps(i, 1, cont.size() - 1) {
			sumLeft[i] = sumLeft[i - 1] + cont[i];
		}
		vll sumRight(cont.size(), 0);
		sumRight[cont.size() - 1] = cont[cont.size() - 1];
		deps(i, cont.size() - 2, 0) {
			sumRight[i] = sumRight[i + 1] + cont[i];
		}
		rep(i, cont.size()) {
			result = max(result, min(sumLeft[i], sumRight[i]));
		}
	}

	printf("%lld\n", result);
}
*/

//AtCoder Beginner Contest 038 - D
/*
struct LLPair {
	ll w = 0;
	ll h = 0;
	LLPair() {}
	LLPair(ll w, ll h) {
		this->w = w;
		this->h = h;
	}
};

int main() {
	ll N;
	scanf("%lld", &N);
	vector<LLPair> P(N);
	vll sameWidthCount(101010, 0);
	ll numOfWidth = 0;
	rep(i, N) {
		ll w;
		scanf("%lld", &w);
		ll h;
		scanf("%lld", &h);
		P[i].w = w;
		P[i].h = h;
		if (sameWidthCount[w] == 0) {
			numOfWidth++;
		}
		sameWidthCount[w]++;
	}

	std::sort(P.begin(), P.end(), [](const LLPair &a, const LLPair &b) {
		if (a.w == b.w) {
			return a.h > b.h; //降順にするには > とする
		}
		else {
			return a.w < b.w; //降順にするには > とする
		}
	});

	rep(j, N) {
		eprintf("%lld ", P[j].w);
	}
	eprintf("\n");
	rep(j, N) {
		eprintf("%lld ", P[j].h);
	}
	eprintf("\n\n");

	vll dp(N, INF); //dp[h / w][最長列数]
	int iP = 0;

	rep(i, numOfWidth) {
		ll loopCount = sameWidthCount[P[iP].w];
		vll writeIndex;
		vll writeValue;

		rep(j, loopCount) {
			ll index = lower_bound(dp.begin(), dp.end(), P[iP].h) - dp.begin();
			writeIndex.push_back(index);
			writeValue.push_back(P[iP].h);
			iP++;
		}
		rep(j, loopCount) {
			dp[writeIndex[j]] = writeValue[j];
		}

		rep(j, N) {
			dp[j] == INF ? eprintf("- ") : eprintf("%lld ", dp[j]);
		}
		eprintf("\n");
	}

	ll result = lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
	printf("%lld\n", result);
}
*/


//AtCoder Beginner Contest 126 - F
/*
ll LLpow(ll x, ll n) {
	ll ret = 1;
	while (n > 0) {
		if (n & 1) {
			ret *= x;
		}
		x *= x;
		n >>= 1;
	}
	return ret;
}

int main() {
	ll M;
	scanf("%lld", &M);
	ll K;
	scanf("%lld", &K);

	if (M == 0) {
		if (K > 0) {
			printf("-1\n");
			return 0;
		}

		printf("0 0\n");
		return 0;
	}
	else if (M == 1) {
		if (K > 0) {
			printf("-1\n");
			return 0;
		}

		printf("0 0 1 1\n");
		return 0;
	}
	else {
		ll N = LLpow(2, M);
		if (K >= N) {
			printf("-1\n");
			return 0;
		}

		vll result;

		result.push_back(K);
		rep(i, N) {
			if (i != K) {
				result.push_back(i);
			}
		}
		result.push_back(K);
		dep(i, N) {
			if (i != K) {
				result.push_back(i);
			}
		}
		for (auto val : result) {
			printf("%lld ", val);
		}
		printf("\n");
	}
}
*/

//AtCoder Beginner Contest 116 - D
/*
struct LLPair {
	ll t = 0;
	ll d = 0;
	LLPair() {}
	LLPair(ll t, ll d) {
		this->t = t;
		this->d = d;
	}
};

bool operator< (const LLPair &p1, const LLPair &p2) {
	return p1.d > p2.d;
};

int main() {
	ll N;
	scanf("%lld", &N);
	ll K;
	scanf("%lld", &K);
	vector<LLPair> pair(N);
	priority_queue<LLPair> pq; //ネタの美味しさ低い順
	vll count(N, 0);
	rep(i, N) {
		ll t;
		scanf("%lld", &t);
		ll d;
		scanf("%lld", &d);
		pair[i].t = t - 1;
		pair[i].d = d;
	}

	std::sort(pair.begin(), pair.end(), [](const LLPair &a, const LLPair &b) {
		return a.d > b.d; //降順にするには > とする
	});

	ll sum_d = 0;
	ll kind = 0;

	rep(i, K) {
		sum_d += pair[i].d;
		if (count[pair[i].t] == 0) {
			kind++;
		}
	
		count[pair[i].t]++;
		pq.push(pair[i]);
	}

	ll result = sum_d + kind * kind;

	ll iPair = K;
	while (pq.empty() == false) {
		//取り除くものを選ぶ
		LLPair item = pq.top();
		pq.pop();

		if (count[item.t] == 1) {
			//ラス１の場合は、取り除くと種類数が減るのでスキップ
			continue;
		}

		count[item.t]--;
		sum_d -= item.d;

		//pair[i]を代わりに入れる
		while (iPair < N) {
			if (count[pair[iPair].t] > 0) {
				//すでにその種類のものが存在する場合は種類数が増えないのでスキップ
				iPair++;
				continue;
			}

			count[pair[iPair].t]++;
			sum_d += pair[iPair].d;
			kind++;

			result = max(result, sum_d + kind * kind);

			iPair++;
			break;
		}

		if (iPair == N) {
			break;
		}
	}

	printf("%lld\n", result);
}
*/

//AtCoder Beginner Contest 065 - D
/*
struct LLPoint {
	ll x = 0;
	ll y = 0;
	ll no = 0;
	LLPoint() {}
	LLPoint(ll no, ll x, ll y) {
		this->no = no;
		this->x = x;
		this->y = y;
	}
};

// グラフテンプレート
template<typename T>
struct edge {
	int src, to;
	T cost;
	edge(int to, T cost) : src(-1), to(to), cost(cost) {}
	edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
	edge &operator=(const int &x) {
		to = x;
		return *this;
	}
	operator int() const { return to; }
};
template<typename T>
using Edges = vector<edge<T>>;
template<typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template<typename T>
using Matrix = vector<vector<T >>;

//Union-Find : O(α(N))
struct UnionFind {
	vector<int> data;
	UnionFind(int sz) {
		data.assign(sz, -1);
	}
	bool unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y) return (false);
		if (data[x] > data[y]) swap(x, y);
		data[x] += data[y];
		data[y] = x;
		return (true);
	}
	int find(int k) {
		if (data[k] < 0) {
			return (k);
		}
		return (data[k] = find(data[k]));
	}
	int size(int k) {
		return (-data[find(k)]);
	}
};

//最小全域木(Kruskal) : O(E * logV)
template<typename T>
T kruskal(Edges<T> &edges, int V) {
	sort(begin(edges), end(edges), [](const edge<T> &a, const edge<T> &b) {
		return (a.cost < b.cost);
	});
	UnionFind tree(V);
	T ret = 0;
	for (auto &e : edges) {
		if (tree.unite(e.src, e.to)) ret += e.cost;
	}
	return (ret);
}

int main() {
	ll N;
	scanf("%lld", &N);
	vector<LLPoint> xSort(N);
	vector<LLPoint> ySort(N);
	rep(i, N) {
		ll x;
		scanf("%lld", &x);
		ll y;
		scanf("%lld", &y);
		xSort[i].no = i;
		xSort[i].x = x;
		xSort[i].y = y;
		ySort[i].no = i;
		ySort[i].x = x;
		ySort[i].y = y;
	}

	std::sort(xSort.begin(), xSort.end(), [](const LLPoint &a, const LLPoint &b) {
		return a.x < b.x; //降順にするには > とする
	});

	std::sort(ySort.begin(), ySort.end(), [](const LLPoint &a, const LLPoint &b) {
		return a.y < b.y; //降順にするには > とする
	});

	Edges<ll> edges;

	rep(i, N - 1) {
		edges.emplace_back(xSort[i].no, xSort[i + 1].no, abs(xSort[i].x - xSort[i + 1].x));
		edges.emplace_back(ySort[i].no, ySort[i + 1].no, abs(ySort[i].y - ySort[i + 1].y));
	}

	ll result = kruskal(edges, (int)N);

	printf("%lld\n", result);
}
*/


Measured memory_bytes: 6656