#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�������̂��܂��Ȃ��{�����w��

ll mll::MOD = (ll)(1e9 + 7);// 998244353ll;


//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) {
		//���݂̏󋵂ł̎Q�����z�𒲍�
		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�̋��Z�s��Ȃ��悤�ɂ��Ď��̒�����
		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����ƌ��̕΂�̐��l��
	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) {
						//�E��
						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):= �T�C�Y n �̏������B������ f ��2�̋�Ԃ̗v�f���}�[�W����񍀉��Z, M1 �̓��m�C�h�̒P�ʌ��ł���B
//set(k, x):= k �Ԗڂ̗v�f�� x ��������B
//build():= �Z�O�����g�؂��\�z����B
//query(a, b):= ��� [a,b) �ɑ΂��ē񍀉��Z�������ʂ�Ԃ��B
//update(k, x):= k �Ԗڂ̗v�f�� x �ɕύX����B
//operator[k] := k �Ԗڂ̗v�f��Ԃ��B
//find_first(a, check) := [a,x) �� check �𖞂����ŏ��̗v�f�ʒu x ��Ԃ��B
//find_last(b, check) := [x,b) �� check �𖞂����Ō�̗v�f�ʒu x ��Ԃ��B

//�g�p��
//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���O���[�v1�Ƃ���
		//i+1�`N-1�܂ł��O���[�v2�Ƃ���
		//0�`i-1���O���[�v1��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���O���[�v1�Ɋ��蓖�Ă�
			{
				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���O���[�v2�Ɋ��蓖�Ă�
			{
				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�̑g�ݍ��킹�ɑ΂��ď��������s����
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];
	}

	//���s��
	foreach_comb(N, P, [](int *indexes) {
		//std::cout << indexes[0] << ',' << indexes[1] << ',' << indexes[2] << ',' << indexes[3] << ',' << indexes[4] << std::endl;
		vector<LLPair> men(M); //�j�q[i]���Q�����邱�Ƃɂ��K���x
		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; //�l�^�̔��������Ⴂ��
	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) {
		//��菜�����̂�I��
		LLPair item = pq.top();
		pq.pop();

		if (count[item.t] == 1) {
			//���X�P�̏ꍇ�́A��菜���Ǝ�ސ�������̂ŃX�L�b�v
			continue;
		}

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

		//pair[i]�����ɓ����
		while (iPair < N) {
			if (count[pair[iPair].t] > 0) {
				//���łɂ��̎�ނ̂��̂����݂���ꍇ�͎�ސ��������Ȃ��̂ŃX�L�b�v
				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;
	}
};

// �O���t�e���v���[�g
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)]);
	}
};

//�ŏ��S���(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: 256