#1172472 (C++23(gcc16)) No.3585 Make Ends Meet (Easy)

• 問題: No.3585 Make Ends Meet (Easy)
• ユーザー: anago-pie
• 提出日時: 2026-07-22 13:49:42
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 42,310 bytes
• コンパイル時間: 4,700 ms
• コンパイル使用メモリ: 394,204 KB
• 実行使用メモリ: 7,808 KB
• 最終ジャッジ日時: 2026-07-22 13:49:50
• 合計ジャッジ時間: 7,100 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_1

ファイルパターン	結果
sample	AC * 2
other	AC * 46 WA * 2

コンパイルメッセージ

main.cpp:12:27: warning: integer overflow in expression of type 'int' results in '2147483647' [-Woverflow]
   12 | const int inf = (1 << 31) - 1;
      |                 ~~~~~~~~~~^~~
main.cpp:13:27: warning: integer overflow in expression of type 'long long int' results in '9223372036854775807' [-Woverflow]
   13 | const ll INF = (1LL << 63)-1;
      |                ~~~~~~~~~~~^~

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define debug 0
#define YES cout << "Yes" << endl;
#define NO cout << "No" << endl;
using ll = long long;
using ld = long double;
const int mod = 998244353;
const int MOD = 1000000007;
const double pi = atan2(0, -1);
const int inf = (1 << 31) - 1;
const ll INF = (1LL << 63)-1;
#include <time.h>
#include <chrono>
#include <atcoder/convolution>
#include <atcoder/modint>
using namespace atcoder;

struct Timer {
	chrono::steady_clock::time_point start;

	Timer() : start(chrono::steady_clock::now()) {}

	// elapsed()でオブジェクト生成からの経過時間をms単位double値で取得できる
	double elapsed() const {
		return chrono::duration<double, milli>(
			chrono::steady_clock::now() - start
		).count();
	}

	// 経過時間を標準入力に出力する（ローカル確認用）
	void print_time(){
		cout<<"---------------------\n■ 実行時間 : "<<ceil(elapsed())<<"ms\n---------------------\n";
	}
};

//vectorの中身を空白区切りで出力
template<typename T> 
void print1(vector<T> v) {
	for (int i = 0; i < v.size(); i++) {
		cout << v[i];
		if (i < v.size() - 1) {
			cout << " ";
		}
	}
}

//vectorの中身を改行区切りで出力
template<typename T>
void print2(vector<T> v) {
	for (auto x : v) {
		cout << x << endl;
	}
}

//二次元配列を出力
template<typename T>
void printvv(vector<vector<T>> vv) {
	for (vector<T> v : vv) {
		print1(v);
		cout << endl;
	}
}

//vectorを降順にソート
template<typename T>
void rsort(vector<T> &v) {
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
}

//昇順priority_queueを召喚
template<typename T>
struct rpriority_queue {
	priority_queue<T, vector<T>, greater<T>> pq;

	void push(T x) {
		pq.push(x);
	}

	void pop() {
		pq.pop();
	}

	T top() {
		return pq.top();
	}

	size_t size() {
		return pq.size();
	}

	bool empty() {
		return pq.empty();
	}
};


//高速10^n計算(mod mod)
ll tenth(int n) {
	if (n == 0) {
		return 1;
	}
	else if (n % 2 == 0) {
		ll x = tenth(n / 2);
		x %= mod;
		x *= x;
		x %= mod;
		return x;
	}
	else {
		ll x = tenth(n - 1);
		x *= 10;
		x %= mod;
		return x;
	}
}


//高速a^n計算
ll power(int a, int n){
	if(n == 0){
		return 1;
	}
	else if(n % 2 == 0){
		ll x = power(a, n / 2);
		x *= x;
		return x;
	}
	else {
		ll x = power(a, n - 1);
		x *= a;
		return x;
	}
}
ld power(ld a, int n){
	if(n==0){
		return 1;
	}
	else if(n%2==0){
		ld t=power(a,n/2);
		return t*t;
	}
	else{
		return a*power(a,n-1);
	}
}

//n以下の素数列を生成
vector<int> prime (int n) {
	vector<bool> ch(n, false);
	vector<int> pr;
	for(int i = 2; i <= n; i++){
		if(!ch[i]){
			pr.push_back(i);
			for(int j = 1; i*j<=n; j++){
				ch[i*j]=true;
			}
		}
	}
	return pr;
}

//最大公約数(ユークリッドの互除法）
ll gcd (ll a, ll b){
	if(b>a){
		swap(a, b);
	}
	while(a%b!=0){
		ll t = a;
		a = b;
		b = t%b;
	}
	return b;
}

//最小公倍数（gcdを定義しておく）
ll lcm (ll a, ll b){
	ll g = gcd(a, b);
	ll x = (a/g)*b;
	return x;
}


//N以上の最小の2冪を返す
ll upper_binary(ll N){
	ll ret=1;
	while(ret<N) ret<<=1LL;
	return ret;
}

//__int128_tの準備
// abs overload for __int128_t to avoid ambiguous call with std::abs
static inline __int128_t abs128(__int128_t x) noexcept {
	return x < 0 ? -x : x;
}

// gcd for __int128_t
static inline __int128_t gcd128(__int128_t a, __int128_t b) noexcept {
	if (a < 0) a = -a;
	if (b < 0) b = -b;
	while (b != 0) {
		__int128_t t = a % b;
		a = b;
		b = t;
	}
	return a;
}

ostream& operator<< (ostream& os, __int128_t a){
	vector<int8_t> v;
	__int128_t b=::abs(a);
	while(b>0){
		v.push_back(b%10);
		b/=10;
	}
	string ret;
	if(a<0){
		ret+='-';
	}
	for(int i=v.size()-1;i>=0;i--){
		ret+=char('0'+v[i]);
	}
	if(ret.length()==0){
		ret+='0';
	}
	os << ret;
	return os;
}



//有理数クラス
class Ratio{
	public:
		Ratio(__int128_t _numerator=0, __int128_t _denominator=1){
			numerator=_numerator;
			denominator=_denominator;
			standardize();
		}

		bool operator== (const Ratio& a) const{
			return (a.numerator==numerator) && (a.denominator==denominator);
		}

		bool operator!= (const Ratio& a) const{
			return (a.numerator!=numerator) || (a.denominator!=denominator); 
		}

		Ratio operator+ (const Ratio& a) const{
			Ratio res(numerator*a.denominator+a.numerator*denominator, denominator*a.denominator);
			return res;
		}

		Ratio& operator+= (const Ratio& a){
			numerator=numerator*a.denominator+a.numerator*denominator;
			denominator*=a.denominator;
			standardize();
			return *this;
		}

		Ratio operator- (const Ratio& a) const{
			Ratio res(numerator*a.denominator - a.numerator*denominator, denominator*a.denominator);
			return res;
		}

		Ratio& operator-= (const Ratio& a){
			numerator=numerator*a.denominator-a.numerator*denominator;
			denominator*=a.denominator;
			standardize();
			return *this;
		}

		Ratio operator* (const Ratio& a) const{
			Ratio res(numerator*a.numerator, denominator*a.denominator);
			return res;
		}

		Ratio& operator*= (const Ratio& a){
			numerator*=a.numerator;
			denominator*=a.denominator;
			standardize();
			return *this;
		}

		Ratio operator/ (const Ratio& a) const{
			Ratio res(numerator*a.denominator, denominator*a.numerator);
			return res;
		}

		Ratio& operator/= (const Ratio& a){
			numerator*=a.denominator;
			denominator*=a.numerator;
			standardize();
			return *this;
		}

		bool operator< (const Ratio& a) const {
			return numerator*a.denominator < a.numerator*denominator;
		}

		bool operator<=(const Ratio& a) const {
			return numerator*a.denominator <= a.numerator*denominator;
		}

		bool operator> (const Ratio& a) const{
			return numerator*a.denominator > a.numerator*denominator;
		}

		bool operator>= (const Ratio& a) const{
			return numerator*a.denominator >= a.numerator*denominator;
		}

		Ratio& operator= (const Ratio& a){
			numerator=a.numerator;
			denominator=a.denominator;
			return *this;
		}

		ld to_ld(){
			return ld(numerator)/ld(denominator);
		}

		double to_double(){
			return double(numerator)/double(denominator);
		}

		// 自身以下の最大の整数を返す
		ll le_integer(){
			ll ret=0;
			if(denominator==1){
				ret=numerator;
			}
			else{
				if(numerator<0){
					ret=numerator/denominator-1;
				}
				else{
					ret=numerator/denominator;
				}
			}
			return ret;
		}

		// 自身以上の最小の整数を返す
		ll ge_integer(){
			ll ret=0;
			if(denominator==1){
				ret=numerator;
			}
			else{
				if(numerator<0){
					ret=numerator/denominator;
				}
				else{
					ret=numerator/denominator+1;
				}
			}
			return ret;
		}

		// 自身の逆数を返す。0なら0を返す
		Ratio inverse(){
			if(numerator==0){
				return Ratio(0,1);
			}
			else{
				return Ratio(denominator,numerator);
			}
		}

		friend ostream& operator<< (ostream& os, const Ratio& a);

	private:
		__int128_t numerator;
		__int128_t denominator;

		void standardize(){
			__int128_t g = gcd128(abs128(numerator), abs128(denominator));
			if(g==0){
				numerator=0;
				denominator=1;
			}
			else{
				numerator/=g;
				denominator/=g;
				if((numerator<0)^(denominator<0)){
					numerator=abs128(numerator)*-1;
					denominator=abs128(denominator);
				}
				else{
					numerator=abs128(numerator);
					denominator=abs128(denominator);
				}
			}
		}

};

ostream& operator<< (ostream& os, const Ratio& a){
	os << a.numerator << "/" <<a.denominator;
	return os;
}

Ratio power(Ratio a, int n){
	if(n==0){
		return Ratio(1,1);
	}
	else if(n%2==0){
		Ratio t=power(a,n/2);
		return t*t;
	}
	else{
		return a*power(a,n-1);
	}
}



//角XYZ(偏角Z→X)の角度（[0,2π)）
double angle(vector<double> X, vector<double> Y, vector<double>Z) {
	vector<double> x = { X[0] - Y[0],X[1] - Y[1] };
	vector<double> z = { Z[0] - Y[0],Z[1] - Y[1] };

	double pre, post;
	pre = atan2(x[1], x[0]);
	post = atan2(z[1], z[0]);
	if (post < 0) {
		post += pi*2;
	}
	if (pre < 0) {
		pre += pi*2;
	}
	if (pre < post) {
		pre += pi * 2;
	}
	return pre - post;
}

//mod mod下で逆元を算出する
//高速a^n計算(mod ver.)
ll mypower(ll a, ll n, ll Mod=mod) {
	if (n == 0) {
		return 1;
	}
	else if (n % 2 == 0) {
		ll x = mypower(a, n / 2,Mod);
		x *= x;
		x %= Mod;
		return x;
	}
	else {
		ll x = mypower(a, n - 1,Mod);
		x *= a;
		x %= Mod;
		return x;
	}
}
//フェルマーの小定理を利用
ll fmodinv(ll p, ll Mod=mod) {
	return mypower(p, Mod - 2,Mod) % Mod;
}

//拡張ユークリッドの互除法によるmod p下逆元
ll modinv(ll a, ll Mod=mod){
	ll x,y;
	// ax + by = 1 の解を[x,y]に格納し、gcd(a,b)を返す:gcdは常に一定
	function<ll(ll,ll)> extgcd=[&](ll a, ll b){

		if(b==0){
			x=1; y=0;
			return a;
		}
		else{
			ll g=extgcd(b, a%b);
			swap(x,y);
			y-=(a/b)*x;
			return g;
		}
	};
	ll g = extgcd(Mod, a);
	if(g==1){
		return (Mod+y%Mod)%Mod;
	}
	else{
		return 0;
	}
}


//整数係数不定方程式 a*x + b*y = cの解[x,y]の一つを見つける。解が無いと[INF,INF]を返す
vector<ll> solve_indefinite_eq(ll a, ll b, ll c){
	ll x,y;
	function<ll(ll,ll)> extgcd=[&](ll a,ll b){
		if(b==0){
			x=1; y=0;
			return a;
		}
		else{
			ll g=extgcd(b,a%b);
			swap(x,y);
			y -= (a/b)*x;
			return g;
		}
	};
	ll g=extgcd(a,b);
	if(c%g==0){
		return {(c/g)*x, (c/g)*y};
	}
	else{
		return {INF,INF};
	}
}

////素因数分解（osa_k法）（前計算O(N)、素数判定O(1)、素因数分解(O(logN)） //エラトステネスの篩の代わりとしても使える(N項のvectorを生成するため、巨大数に対しては√Nまでの素数リストを作って割る方が良い)
struct osa_k {
	//最大値までの各自然数に対し、その最小の素因数を格納するリスト
	vector<int> min_prime_list;
	int upper_limit;
	osa_k(int N) {
		//N:最大値。一つの自然数の素因数分解にしか興味が泣ければそれを入力
		vector<int> v(N + 1);
		upper_limit = N;
		rep(i, N + 1) {
			v[i] = i;
		}
		swap(min_prime_list, v);

		//k=2から見る
		for (int k = 2; k * k <= N; k++) {
			if (min_prime_list[k] == k) {
				//最小の素因数=自分ならば、素数
				//kが素数の時、t=k*kから始めてt=Nまでのkの倍数全てを確認する。未更新の自然数があれば、それの最小の素因数をkに更新する。
				//k*k未満のkの倍数に対しては、kが最小の素因数にはなり得ないので計算する必要が無い
				for (int t = k * k; t <= N; t += k) {
					if (min_prime_list[t] == t) {
						min_prime_list[t] = k;
					}
				}
			}
		}
	}

	//任意の自然数nが素数であればtrueを返す
	bool isPrime(int n) {
		if (n < 2) {
			return false;
		}
		else {
			return min_prime_list[n] == n;
		}
	}

	//任意の自然数nの素因数分解を行う。素因数はvectorで与えられる（ex:n=12 -> {2,2,3}）
	vector<int> divPrimes(int n) {
		vector<int> vec;
		int now = n;
		while (now > 1) {
			vec.push_back(min_prime_list[now]);
			now /= min_prime_list[now];
		}
		return vec;
	}
};


//最大流問題を解く構造体(Ford-Fulkerson法.O(FE))
struct maxflow {
	struct Edge {
		int to, rev;
		ll capacity, init_capacity;
		int off, on;
		Edge(int _to, int _rev, ll _capacity, int _off, int _on) :to(_to), rev(_rev), capacity(_capacity), init_capacity(_capacity), off(_off), on(_on) {};
	};
	int delay=0;
	
	vector<vector<Edge>> Graph;

	maxflow(int MAX_V, int d) {
		Graph.assign(MAX_V, {});
		delay=d;
	}

	void input(int from, int to, ll capacity, int off, int on) {
		int e_id = Graph[from].size();
		int r_id = Graph[to].size();
		Graph[from].push_back(Edge(to, r_id, capacity, off, on));
		Graph[to].push_back(Edge(from, e_id, 0, on+delay, off-delay));
	}

	Edge& rev_Edge(Edge& edge) {
		return Graph[edge.to][edge.rev];
	}

	vector<bool> visited;
	ll dfs(int now, int g, ll flow, int time) {
		visited[now] = true;
		if (now == g) {
			return flow;
		}
		else {
			ll f = 0;
			ll res_flow = flow;
			for (Edge& edge : Graph[now]) {
				if (!visited[edge.to] && edge.capacity > 0 && edge.off>=time && edge.on<=1e9) {
					ll f_delta = dfs(edge.to, g, min(res_flow, edge.capacity), edge.on+delay);	
					edge.capacity -= f_delta;
					rev_Edge(edge).capacity += f_delta;
					f += f_delta;
					res_flow -= f_delta;
					if (res_flow == 0) {
						break;
					}
				}
			}
			return f;
		}
	}

	void flowing(int s, int g, ll init_flow = INF) {
		bool cont = true;
		while (cont) {
			visited.assign(Graph.size(), false);
			ll flow = dfs(s, g, init_flow,0);
			init_flow -= flow;
			if (flow == 0) {
				cont = false;
			}
		}
	}

	ll get_flow(int g) {
		ll flow = 0;
		for (Edge& edge : Graph[g]) {
			Edge& rev_edge = rev_Edge(edge);
			ll tmp_flow = rev_edge.init_capacity - rev_edge.capacity;
			if (tmp_flow > 0) {
				flow += tmp_flow;
			}
		}
		return flow;
	}

	vector<tuple<int, int, ll>> flowing_edges() {
		vector<tuple<int, int, ll>> vec;
		rep(from, Graph.size()) {
			for (Edge& edge : Graph[from]) {
				ll flow = edge.init_capacity - edge.capacity;
				if (flow > 0) {
					vec.push_back({ from,edge.to,flow });
				}
			}
		}
		return vec;
	}
};

//Dinic法でのmax-flow。最大マッチングなど辺のキャパシティが小さい場合には高速
struct Dinic {
	struct Edge {
		int to, rev;
		ll capacity, init_capacity;
		ld cost;
		Edge(int _to, int _rev, ll _capacity,ld _cost) :to(_to), rev(_rev), capacity(_capacity),init_capacity(_capacity),cost(_cost) {};
	};

	vector<vector<Edge>> Graph;

	Edge& rev_Edge(Edge& edge) {
		return Graph[edge.to][edge.rev];
	}
	vector<int> level,itr;

	Dinic(int MAX_V) {
		Graph.assign(MAX_V, {});
	}

	void input(int _from, int _to, ll _capacity,ld _cost) {
		int e_id = Graph[_from].size(), r_id = Graph[_to].size();
		Graph[_from].push_back(Edge(_to, r_id, _capacity,_cost));
		Graph[_to].push_back(Edge(_from, e_id, 0LL,_cost));
	}

	void bfs(int s, int g, ld val) {
		level.assign(Graph.size(), -1);
		level[s] = 0;
		queue<int> q;
		q.push(s);
		while (!q.empty()) {
			int now = q.front();
			q.pop();
			if (now == g) {
				continue;
			}
			for (Edge &e : Graph[now]) {
				if (level[e.to] == -1 && e.capacity > 0 && e.cost<=val) {
					level[e.to] = level[now] + 1;
					q.push(e.to);
				}
			}
		}
	}

	ll dfs(int now, int g, ll flow, ld val) {
		if (now == g) {
			return flow;
		}
		else if (level[now] >= level[g]) {
			return 0; //gよりも深い場所に行こうとしたら終わり。flow=0を返す
		}
		else {
			ll res_flow = flow;
			ll f = 0;
			for (int &i = itr[now]; i < Graph[now].size(); i++) {
				Edge& edge = Graph[now][i];
				if (level[edge.to] == level[now] + 1 && edge.capacity > 0 && edge.cost<=val) {
					ll f_delta = dfs(edge.to, g, min(res_flow, edge.capacity), val);
					edge.capacity -= f_delta;
					rev_Edge(edge).capacity += f_delta;
					res_flow -= f_delta;
					f += f_delta;
					if (res_flow == 0) {
						break;
					}
				}
			}
			return f; //行先が無い場合はflow=0を返す
		}
	}

	void flowing(int s, int g, ll init_flow = INF, ld val=0) {
		bool cont1 = true;
		while (cont1) {
			bfs(s, g,val);
			if (level[g] == -1) {
				cont1 = false;
			}
			else {
				bool cont2 = true;
				while (cont2) {
					itr.assign(Graph.size(), 0);
					ll flow = dfs(s, g, init_flow,val);
					init_flow -= flow;
					if (flow == 0) {
						cont2 = false;
					}
				}
			}
			if(init_flow==0){
				cont1=false;
			}
		}
	}

	ll get_flow(int g) {
		ll flow = 0;
		for (Edge& edge : Graph[g]) {
			flow += max(0LL, rev_Edge(edge).init_capacity - rev_Edge(edge).capacity);
		}
		return flow;
	}

	vector<tuple<int, int, ll>> flowing_edges(){
		vector<tuple<int,int,ll>> vec;
		for (int from = 0; from < Graph.size(); from++) {
			for (Edge& edge : Graph[from]) {
				if (edge.init_capacity - edge.capacity > 0) {
					vec.push_back({ from,edge.to,edge.init_capacity - edge.capacity });
				}
			}
		}
		return vec;
	}

	void reset() {
		for (int from = 0; from < Graph.size(); from++) {
			for (Edge& edge : Graph[from]) {
				edge.capacity = edge.init_capacity;
			}
		}
	}
};

//小さい方/大きい方からk番目の値を取り出せる平衡二分木
template<typename T>
struct ordered_set{
	public:
		int root=0;
		struct node{
			T value;
			int size;
			int par;
			int left;
			int right;
			int weight;
			int id;
			int count;
			node(T _value){
				par=0;
				left=0;
				right=0;
				size=0;
				weight=0;
				id=0;
				count=1;
				value=_value;
			}

			auto operator <=> (node& a){
				return value <=> a.value;
			}

			bool operator == (node& a){
				return value==a.value;
			}
		};
		vector<node> list;
		bool multi;

		ordered_set(bool multi_mode=false){
			list.emplace_back(node(T()));
			multi=multi_mode;
		}

		void r_rotate(int partial_root){
			if(partial_root==0) return;
			node* now= &list[partial_root];
			node* par= &list[now->par];
			node* child= &list[now->left];
			int& edge = (*par)>(*now)? par->left : par->right;

			if(list[child->left].weight >= list[child->right].weight){		
				edge=now->left;
				child->par = now->par;
				now->left = child->right;
				list[child->right].par=partial_root;
				child->right=partial_root;
				now->par = edge;

				update(now);
				update(child);
				update(par);
			}
			else{
				node* grand= &list[child->right];
				
				edge=child->right;
				grand->par=now->par;
				child->right=grand->left;
				list[grand->left].par=now->left;
				grand->left=now->left;
				child->par=edge;
				now->left=grand->right;
				list[grand->right].par=partial_root;
				grand->right=partial_root;
				now->par=edge;

				update(child);
				update(now);
				update(grand);
				update(par);
			}	
			
			if(par== &list[0]){
				root=edge;
			}
		}

		void l_rotate(int partial_root){
			if(partial_root==0) return;
			node* now= &list[partial_root];
			node* par= &list[now->par];
			node* child= &list[now->right];
			int& edge = (*par)>(*now)? par->left : par->right;

			if(list[child->right].weight >= list[child->left].weight){		
				edge=now->right;
				child->par = now->par;
				now->right = child->left;
				list[child->left].par=partial_root;
				child->left=partial_root;
				now->par = edge;

				update(now);
				update(child);
				update(par);
			}
			else{
				node* grand= &list[child->left];
				
				edge=child->left;
				grand->par=now->par;
				child->left=grand->right;
				list[grand->right].par=now->right;
				grand->right=now->right;
				child->par=edge;
				now->right=grand->left;
				list[grand->left].par=partial_root;
				grand->left=partial_root;
				now->par=edge;

				update(child);
				update(now);
				update(grand);
				update(par);
			}

			if(par==&list[0]){
				root=edge;
			}
		}

		void insert(T x){
			if(root==0){
				int id=list.size();
				list.emplace_back(node(x));
				root=id;
				update(&list[id]);
			}
			else{
				int now=root;
				int pre=0;
				bool correct=true;
				while(correct && now!=0){
					if(multi && list[now].value==x){
						correct=false;
						list[now].count++;
						list[now].size++;
						break;
					}
					if(!multi && list[now].value==x){
						return;
					}
					if(list[now].value>=x){
						pre=now;
						now=list[now].left;
					}
					else{
						pre=now;
						now=list[now].right;
					}
				}

				if(correct){
					now=list.size();
					list.push_back(node(x));
					update(&list[now]);
					list[now].par=pre;
					if(list[pre]>=list[now]){
						list[pre].left=now;
					}
					else{
						list[pre].right=now;
					}
				}
				
				while(now!=0){
					update(&list[now]);
					if(list[list[now].right].weight>=list[list[now].left].weight+2){
						l_rotate(now);
					}
					else if(list[list[now].left].weight>=list[list[now].right].weight+2){
						r_rotate(now);
					}
					now=list[now].par;
				}
			}
		}

		void erase(T x){
			int now=search(x);
			if(now==0){
				return;
			}
			list[now].count--;
			if(list[now].count==0){
				int state=-1;
				if(list[now].par!=0){
					if(list[list[now].par]>=list[now]){
						state=0;
					}
					else{
						state=1;
					}
				}
				while(list[now].left!=0 || list[now].right!=0){
					if(list[list[now].left].weight>=list[list[now].right].weight){
						r_rotate(now);
						state=1;
					}
					else{
						l_rotate(now);
						state=0;
					}
				}
				
				now=list[now].par;
				if(state==0){
					list[list[now].left].par=0;
					list[now].left=0;
				}
				else if(state==1){
					list[list[now].right].par=0;
					list[now].right=0;
				}
				if(now==0){
					root=0;
				}
			}

			while(now!=0){
				update(&list[now]);
				if(list[list[now].left].weight>=list[list[now].right].weight+2){
					r_rotate(now);
				}
				else if(list[list[now].right].weight>=list[list[now].left].weight+2){
					l_rotate(now);
				}
				now=list[now].par;
			}

			if(list.size()>=20000000 && list[now].size*2<list.size()){
				compress();
			}
		}

		int count(T x){
			int now=search(x);
			return now==0? 0:list[now].count;
		}

		int size(){
			return root==0? 0:list[root].size;
		}

		// xより小さい最大の値を返す 該当値がなければnullに指定された値を返す
		T lower_value(T x, T null){
			int now=root;
			T* ret=nullptr;
			while(now!=0){
				if(list[now].value<x){
					if(!ret){
						ret= &list[now].value;
					}
					else{
						ret= *ret<list[now].value? &list[now].value:ret;
					}
					now=list[now].right;
				}
				else{
					now=list[now].left;
				}
			}
			return ret? *ret:null;
		}

		// x以下の最大の値を返す 該当値がなければnullに指定された値を返す
		T lower_or_equal_value(T x, T null){
			int now=root;
			T* ret=nullptr;
			while(now!=0 && (!ret || *ret!=x)){
				if(list[now].value<=x){
					if(!ret){
						ret= &list[now].value;
					}
					else{
						ret= *ret<list[now].value ? &list[now].value:ret;
					}
					now=list[now].right;
				}
				else{
					now=list[now].left;
				}
			}
			return ret? *ret:null;
		}

		// xより大きい最小の値を返す 該当値がなければnullに指定された値を返す
		T upper_value(T x, T null){
			int now=root;
			T* ret=nullptr;
			while(now!=0){
				if(list[now].value>x){
					if(!ret){
						ret= &list[now].value;
					}
					else{
						ret= *ret>list[now].value?&list[now].value:ret;
					}
					
					now=list[now].left;
				}
				else{
					now=list[now].right;
				}
			}
			return ret? *ret:null;
		}

		// x以上の最小の値を返す 該当値がなければnullに指定された値を返す
		T upper_or_equal_value(T x, T null){
			int now=root;
			T* ret=nullptr;
			while(now!=0 && (!ret || *ret!=x)){
				if(list[now].value>=x){
					if(!ret){
						ret= &list[now].value;
					}
					else{
						ret= *ret>list[now].value? &list[now].value:ret;
					}
					now=list[now].left;
				}
				else{
					now=list[now].right;
				}
			}
			return ret? *ret:null;
		}

		// xより小さい値の個数を返す
		int lower_count(T x){
			int now=root;
			int ret=0;
			while(now!=0){
				if(list[now].value<x){
					ret+=list[list[now].left].size + list[now].count;
					now=list[now].right;
				}
				else if(list[now].value>x){
					now=list[now].left;
				}
				else{
					ret+=list[list[now].left].size;
					break;
				}
			}
			return ret;
		}

		// x以下の値の個数を返す
		int lower_or_equal_count(T x){
			int now=root;
			int ret=0;
			while(now!=0){
				if(list[now].value<x){
					ret+=list[list[now].left].size + list[now].count;
					now=list[now].right;
				}
				else if(list[now].value>x){
					now=list[now].left;
				}
				else{
					ret+=list[list[now].left].size + list[now].count;
					break;
				}
			}
			return ret;
		}

		// xより大きい値の個数を返す
		int upper_count(T x){
			int now=root;
			int ret=0;
			while(now!=0){
				if(list[now].value>x){
					ret+=list[list[now].right].size + list[now].count;
					now=list[now].left;
				}
				else if(list[now].value<x){
					now=list[now].right;
				}
				else{
					ret+=list[list[now].right].size;
					break;
				}
			}
			return ret;
		}

		// x以上の値の個数を返す
		int upper_or_equal_count(T x){
			int now=root;
			int ret=0;
			while(now!=0){
				if(list[now].value>x){
					ret+=list[list[now].right].size + list[now].count;
					now=list[now].left;
				}
				else if(list[now].value<x){
					now=list[now].right;
				}
				else{
					ret+=list[list[now].right].size + list[now].count;
					break;
				}
			}
			return ret;
		}

		// 小さい方からk番目の値を返す. kは1-indexed. 該当値が無ければnullに指定された値を返す
		T kth_min_value(int k, T null){
			if(size()<k) return null;
			int now=root;
			T* ret=nullptr;
			int count=0;
			while(!ret){
				if(count+list[list[now].left].size>=k){
					now=list[now].left;
				}
				else{
					count+=list[list[now].left].size;
					if(count+list[now].count>=k){
						ret=&list[now].value;
					}
					else{
						count+=list[now].count;
						now=list[now].right;
					}
				}
			}
			return ret? *ret:null;
		}

		// 大きい方からk番目の値を返す. kは1-indexed. 該当値が無ければnullに指定された値を返す
		T kth_max_value(int k, T null){
			if(size()<k) return null;
			int now=root;
			T* ret=nullptr;
			int count=0;
			while(!ret){
				if(count+list[list[now].right].size>=k){
					now=list[now].right;
				}
				else{
					count+=list[list[now].right].size;
					if(count+list[now].count>=k){
						ret= &list[now].value;
					}
					else{
						count+=list[now].count;
						now=list[now].left;
					}
				}
			}
			return ret? *ret:null;
		}


	private:
		int search(T x){
			int now=root;
			while(now!=0){
				if(list[now].value==x){
					break;
				}
				if(list[now].value>x){
					now=list[now].left;
				}
				else{
					now=list[now].right;
				}
			}
			return now;
		}

		void compress(){
			int N=list.size();
			vector<node> tmp;
			vector<int> convert(N,-1);
			rep(i,N){
				if(list[i].par!=0 || i==0 || i==root){
					tmp.emplace_back(list[i]);
					convert[i]=tmp.size()-1;
				}
			}
			swap(tmp,list);
			for(node &n:list){
				n.par=convert[n.par];
				n.left=convert[n.left];
				n.right=convert[n.right];
			}
			root=convert[root];
		}

		void update(node* n){
			if(n == &list[0]){
				return;
			}
			n->size=list[n->left].size + list[n->right].size + n->count;
			n->weight=max(list[n->left].weight, list[n->right].weight)+1;
		}
};

//Z-algorithm: 長さNの配列（主に文字列）を渡したとき、i番目の要素から始まる連続部分列のprefixと元の配列のprefixの最長一致数を配列として出力する
template <typename T>
vector<int> Zalgorithm(T &V){
	int n=V.size();
	vector<int> prefix_length(n,0);
	prefix_length[0]=n;
	function<void (int,int)> calc=[&](int start, int range_end){
		if(start>=n){
			return;
		}
		int wide=range_end-start;
		while(start+wide<n && V[wide]==V[start+wide]){
			wide++;
		}
		prefix_length[start]=wide;
		for(int i=0;i<wide;i++){
			if(i+prefix_length[i]<wide){
				prefix_length[start+i]=prefix_length[i];
			}
			else if(i+prefix_length[i]>wide){
				prefix_length[start+i]=wide-i;
			}
			else{
				calc(start+i, start+wide-1);
				return;
			}
		}
		int next=max(start+1, start+wide);
		calc(next,next);
		return;
	};
	calc(1,1);
	return prefix_length;
}

// オイラーツアーできる木構造:共通最小祖先（LCA）
struct EulerTour{
	vector<vector<int>> edge;
	vector<int> par;
	vector<vector<int>> child;
	int n;
	int root;
	struct move{
		int from;
		int to;
		move(int _from, int _to):from(_from), to(_to){};
	};
	struct node{
		int in=-1;
		int out=-1;
		int depth=-1;
	};

	vector<move> moves;
	vector<node> nodes;


	struct segtree{
		struct stnode{
			int index;
			int depth;
			stnode(int _index=-1, int _depth=inf):index(_index), depth(_depth){};
		};

		stnode min(stnode a, stnode b){
			if(a.depth<=b.depth){
				return a;
			}
			else{
				return b;
			}
		};

		vector<stnode> tree;
		int stn=1;

		segtree(int N=2){
			while(stn<N){
				stn*=2;
			}
			tree.assign(stn*2, stnode());
		}

		void input(int step, int index, int depth){
			int now=stn-1+step;
			tree[now].depth=depth;
			tree[now].index=index;
			while(now>0){
				now = (now-1)/2;
				tree[now]=min(tree[now*2+1], tree[now*2+2]);
			}
		}

		stnode Min(int l, int r, int b, int u, int now){

			stnode ret;
			if(l>=u || r<=b){
				ret = stnode();
			}
			else if(l<= b && r>=u){
				ret = tree[now];
			}
			else{
				ret = min(Min(l,r,b,(b+u)/2,now*2+1), Min(l,r,(b+u)/2,u,now*2+2));
			}
			return ret;
		}

		stnode queryMin(int l, int r){
			return Min(l,r,0,stn,0);
		}
	};

	segtree st;

	EulerTour(int N){
		n=N;
		edge.assign(n,{});
		par.assign(n,-1);
		child.assign(n,{});
		nodes.assign(n,node());
		st = segtree(n*2);
	}

	void inputEdge(int a, int b){
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	void _createTree(int _root=0){
		root=_root;
		par[root]=root;
		queue<int> q;
		q.push(0);
		while(!q.empty()){
			int now=q.front();
			q.pop();
			for(int x:edge[now]){
				if(par[x]==-1){
					par[x]=now;
					child[now].push_back(x);
					q.push(x);
				}
			}
		}
	}

	void tour(int _root=0){
		_createTree(_root);
		int step=0;
		moves.push_back(move(-1,root));
		function<void(int, int)> dfs = [&](int now, int depth){
			nodes[now].in=step;
			nodes[now].depth=depth;
			step++;
			for(int x:child[now]){
				moves.push_back(move(now, x));
				dfs(x,depth+1);
			}
			nodes[now].out=step;
			moves.push_back(move(now, par[now]));
			step++;
		};
		dfs(root,0);
		rep(i,moves.size()){
			st.input(i,moves[i].to, nodes[moves[i].to].depth);
		}
	}

	int lca(int x, int y){
		int mini = min(nodes[x].in, nodes[y].in);
		int maxi=max(nodes[x].out, nodes[y].out);
		return st.queryMin(mini,maxi).index;
	}
};


//抽象化セグメント木1 - 一点更新区間取得
template <typename T>
struct absSegTree{
	vector<T> tree;
	int n=1;
	T def;
	absSegTree(int N, T _default){
		while(n<N){
			n*=2;
		}
		def=_default;
		tree.assign(n*2, _default);
	}

	//値a,bから計算結果を返す
	virtual T get_op(T a, T b){
		T ret;
		return ret;
	}

  //値更新の計算
	virtual T update_op(T pre_value, T delta){
		T ret;
		return ret;
	}

	void input(int i, T val){
		int now=n-1+i;
		tree[now]=val;
		while(now>0){
			now=(now-1)/2;
			tree[now]=get_op(tree[now*2+1], tree[now*2+2]);
		}
	}

	void update_query(int i, T x){
		int now=n-1+i;
		tree[now]=update_op(tree[now], x);
		while(now>0){
			now=(now-1)/2;
			tree[now]=get_op(tree[now*2+1], tree[now*2+2]);
		}
	}

	T range_val(int l, int r, int b, int u, int now){
		if(l>=u || r<=b){
			return def;
		}
		else if(l<=b && r>=u){
			return tree[now];
		}
		else{
			return get_op(range_val(l,r,b,(b+u)/2,now*2+1),range_val(l,r,(b+u)/2,u,now*2+2));
		}
	}

	T get_query(int l, int r){
		return range_val(l,r,0,n,0);
	}
};

//抽象化セグメント木2 - 区間更新一点取得(双対セグメント木)
template<typename T>
struct absDualSegTree{
	vector<T> tree;
	int n=1;
	T def;
	absDualSegTree(int N, T _default){
		while(n<N){
			n*=2;
		}
		def=_default;
		tree.assign(n*2,def);
	}

	//作用素ツリーの更新
	virtual T update_op(T a, T b){
		T ret;
		return ret;
	}

	//作用素を作用させた結果を返す
	virtual T get_op(T pre_value, T f){
		T ret;
		return ret;
	}

	void input(int i, T val){
		int now=n-1+i;
		tree[now]=val;
	}

	void range_update(int l, int r, int b, int u, T x, int now){
		if(l>=u || r<= b){
			return;
		}
		else if(l<=b && r>=u){
			tree[now]=update_op(tree[now], x);
		}
		else{
			range_update(l,r,b,(b+u)/2,x,now*2+1);
			range_update(l,r,(b+u)/2,u,x,now*2+2);
		}
	}

	void update_query(int l, int r, T x){
		range_update(l,r,0,n,x,0);
	}

	T get_query(int i){
		int now=n-1+i;
		T ret=get_op(def,tree[now]);
		while(now>0){
			now=(now-1)/2;
			ret=get_op(ret,tree[now]);
		}
		return ret;
	}
};

//抽象化遅延伝搬セグメント木 - 区間更新区間取得（Lazy Segment Tree）
template<typename treeT, typename lazyT>
struct absLazySegTree{
	vector<treeT> tree;
	vector<lazyT> lazy;
	int n=1;
	treeT tree_default;
	lazyT lazy_default;
	
	absLazySegTree(int N, treeT _tree_default=0, lazyT _lazy_default=0):tree_default(_tree_default), lazy_default(_lazy_default){
		while(n<N){
			n*=2;
		}
		tree.assign(n*2, tree_default);
		lazy.assign(n*2, _lazy_default);
	}

	void input(int i, treeT x){
		int now=n-1+i;
		tree[now]=x;
		while(now>0){
			now=(now-1)/2;
			tree[now]=get_op(tree[now*2+1],tree[now*2+2]);
		}
	}

	// lazy-treeの作用素同士の結合写像
	virtual lazyT lazy_update_op(lazyT pre, lazyT delta){
		return lazy_default;
	}

	// lazy-treeの作用素をtreeのノードに作用させる写像
	virtual treeT lazy_to_tree_op(int now, treeT pre, lazyT delta){
		return tree_default;
	}

	// 2つのtreeのノードを合成する写像
	virtual treeT get_op(treeT a, treeT b){
		return tree_default;
	}
	

	void update_query(int l, int r, lazyT x){
		lazy_update(l,r,0,n,0,x);
	}

	treeT get_query(int l, int r){
		pre_get(l,r,0,n,0);
		return tree_get(l,r,0,n,0);
	}

	private: 
		void lazy_update(int l, int r, int b, int u, int now, lazyT x){
			if(l>=u || r<=b){
				if(lazy[now]!=lazy_default){
					tree[now]=lazy_to_tree_op(now, tree[now],lazy[now]);
					lazy_propagate(now);
				}
			}
			else if(l<=b && r>=u){
				lazy[now]=lazy_update_op(lazy[now], x);
				if(lazy[now]!=lazy_default){
					tree[now]=lazy_to_tree_op(now, tree[now],lazy[now]);
					lazy_propagate(now);
				}
			}
			else{
				if(lazy[now]!=lazy_default){
					lazy_propagate(now);	
				}
				lazy_update(l,r,b,(b+u)/2,now*2+1,x);
				lazy_update(l,r,(b+u)/2,u,now*2+2,x);
				tree[now]=get_op(tree[now*2+1],tree[now*2+2]);
			}
		}

		void lazy_propagate(int now){
			if(now<n-1){
				lazy[now*2+1]=lazy_update_op(lazy[now*2+1], lazy[now]);
				lazy[now*2+2]=lazy_update_op(lazy[now*2+2], lazy[now]);
			}
			lazy[now]=lazy_default;
		}

		void pre_get(int l, int r, int b, int u, int now){
			if(l>=u || r<=b){
				if(lazy[now]!=lazy_default){
					tree[now]=lazy_to_tree_op(now, tree[now], lazy[now]);
					lazy_propagate(now);
				}
			}
			else if(l<=b && r>=u){
				if(lazy[now]!=lazy_default){
					tree[now]=lazy_to_tree_op(now, tree[now], lazy[now]);
					lazy_propagate(now);
				}
			}
			else{
				if(lazy[now]!=lazy_default){
					lazy_propagate(now);
				}
				pre_get(l,r,b,(b+u)/2,now*2+1);
				pre_get(l,r,(b+u)/2,u,now*2+2);
				tree[now]=get_op(tree[now*2+1],tree[now*2+2]);
			}
		}

		treeT tree_get(int l, int r, int b, int u, int now){
			if(l>=u || r<=b){
				return tree_default;
			}
			else if(l<=b && r>=u){
				return tree[now];
			}
			else{
				return get_op(tree_get(l,r,b,(b+u)/2,now*2+1), tree_get(l,r,(b+u)/2,u,now*2+2));
			}
		}
};

//永続セグメント木 - バージョン管理できるセグ木 一点更新区間取得
template<typename T>
struct absPerSegTree{
	T def;
	int n=1;
	struct node{
		T value;
		int par;
		int left;
		int right;
		node(T v, int p=-1, int l=-1, int r=-1):par(p),left(l),right(r){
			value=v;
		}
	};
	vector<node> tree;
	unordered_map<int,int> version_root;

	absPerSegTree(int N, T _default){
		def=_default;
		while(n<N) n<<=1;
		node def_node(def);
		tree.assign(n*2, def_node);
		rep(now,n*2-1){
			if(now!=0){
				tree[now].par=(now-1)/2;
			}
			if(now<n-1){
				tree[now].left=now*2+1;
				tree[now].right=now*2+2;
			}
		}
		version_root[0]=0;
	}

	void input(int i, T x){
		int now=n-1+i;
		tree[now]=x;
		while(now>0){
			now=(now-1)/2;
			tree[now].value=get_op(tree[now*2+1].value, tree[now*2+2].value);
		}
	}
	
	void update_query(int i, T x, int pre_version, int neo_version){
		int l=0, r=n;
		int pre_now=version_root[pre_version];
		version_root[neo_version]=tree.size();
		int neo_now=-1;
		int neo_par=-1;
		while(true){
			tree.push_back(tree[pre_now]);
			neo_now=tree.size()-1;
			tree[neo_now].par=neo_par;
			if(r>l+1){
				if((l+r)/2>i){
					// leftに移動
					tree[neo_now].left=tree.size();
					pre_now=tree[pre_now].left;
					r=(l+r)/2;
				}
				else{
					// rightに移動
					tree[neo_now].right=tree.size();
					pre_now=tree[pre_now].right;
					l=(l+r)/2;
				}
				neo_par=neo_now;
			}
			else{
				break;
			}
		}

		tree[neo_now].value=update_op(tree[neo_now].value, x);
		while(neo_now!=version_root[neo_version]){
			neo_now=tree[neo_now].par;
			tree[neo_now].value=get_op(tree[tree[neo_now].left].value,tree[tree[neo_now].right].value);
		}
	}

	T _get(int l, int r, int b, int u, int now){
		if(l>=u || r<=b){
			return def;
		}
		else if(l<=b && r>=u){
			return tree[now].value;
		}
		else{
			return get_op(_get(l,r,b,(b+u)/2,tree[now].left), _get(l,r,(b+u)/2,u,tree[now].right));
		}
	}

	T get_query(int l, int r, int version){
		int root=version_root[version];
		return _get(l,r,0,n,root);
	}
	

	virtual T update_op(T pre, T delta){
		return def;
	}

	virtual T get_op(T left, T right){
		return def;
	}
};

//永続セグメント木 - バージョン管理できるセグ木 区間更新区間取得
template<typename treeT, typename lazyT>
struct absPerLazySegTree{
	treeT tree_default;
	lazyT lazy_default;
	int n=1;
	struct node{
		treeT value;
		lazyT lazy;
		int left;
		int right;
		node(treeT v, lazyT la, int l=-1, int r=-1):left(l),right(r){
			value=v;
			lazy=la;
		}
	};
	vector<node> tree;
	unordered_map<int,int> version_root;

	absPerLazySegTree(int N, treeT _tree_default, lazyT _lazy_default){
		tree_default=_tree_default;
		lazy_default=_lazy_default;
		while(n<N) n<<=1;
		node def_node(tree_default,lazy_default);
		tree.assign(n*2, def_node);
		rep(now,n*2-1){
			if(now<n-1){
				tree[now].left=now*2+1;
				tree[now].right=now*2+2;
			}
		}
		version_root[0]=0;
	}

	void input(int i, treeT x){
		int now=n-1+i;
		tree[now].value=x;
		while(now>0){
			now=(now-1)/2;
			tree[now].value=get_op(tree[now*2+1].value, tree[now*2+2].value);
		}
	}
	
	void update_query(int l, int r, lazyT x, int pre_version, int neo_version){
		int pre_now=version_root[pre_version];
		version_root[neo_version]=tree.size();
		tree.push_back(tree[pre_now]);
		lazy_update(l,r,0,n,version_root[neo_version],x);
	}

	treeT get_query(int l, int r, int version){
		int root=version_root[version];
		return _get(l,r,0,n,root);
	}

	// lazy-treeの作用素同士の結合写像
	virtual lazyT lazy_update_op(lazyT pre, lazyT delta){
		return lazy_default;
	}

	// lazy-treeの作用素をtreeのノードに作用させる写像
	virtual treeT lazy_to_tree_op(int now, treeT pre, lazyT delta){
		return tree_default;
	}

	// 2つのtreeのノードを合成する写像
	virtual treeT get_op(treeT a, treeT b){
		return tree_default;
	}

	private:
		void lazy_update(int l, int r, int b, int u, int now, lazyT x){
			if(l>=u || r<=b){
				if(tree[now].lazy!=lazy_default){
					tree[now].value=lazy_to_tree_op(now, tree[now].value,tree[now].lazy);
					lazy_propagate(now);
				}
			}
			else if(l<=b && r>=u){
				tree[now].lazy=lazy_update_op(tree[now].lazy, x);
				if(tree[now].lazy!=lazy_default){
					tree[now].value=lazy_to_tree_op(now, tree[now].value,tree[now].lazy);
					lazy_propagate(now);
				}
			}
			else{
				lazy_propagate(now);	
				lazy_update(l,r,b,(b+u)/2, tree[now].left, x);
				lazy_update(l,r,(b+u)/2,u,tree[now].right, x);
				tree[now].value=get_op(tree[tree[now].left].value,tree[tree[now].right].value);
			}
		}

		void lazy_propagate(int now){
			if(tree[now].left!=-1){
				int k=tree.size();
				tree.push_back(tree[tree[now].left]);
				if(tree[now].lazy!=lazy_default){
					tree[k].lazy=lazy_update_op(tree[k].lazy, tree[now].lazy);
				}
				tree[now].left=k;
			}
			if(tree[now].right!=-1){
				int k=tree.size();
				tree.push_back(tree[tree[now].right]);

				if(tree[now].lazy!=lazy_default){
					tree[k].lazy=lazy_update_op(tree[k].lazy, tree[now].lazy);
				}
				tree[now].right=k;
			}
			tree[now].lazy=lazy_default;
		}

		treeT _get(int l, int r, int b, int u, int now){
			if(tree[now].lazy!=lazy_default){
				tree[now].value=lazy_to_tree_op(now, tree[now].value, tree[now].lazy);
				lazy_propagate(now);
			}
			if(l>=u || r<=b){
				return tree_default;
			}
			else if(l<=b && r>=u){
				return tree[now].value;
			}
			else{
				return get_op(_get(l,r,b,(b+u)/2,tree[now].left), _get(l,r,(b+u)/2,u,tree[now].right));
			}
		}
};


template<typename T>
vector<T> comvol(vector<T> A, vector<T> B){
	
};

//-----------------------ここまでライブラリ-----------------------------//

int main(){
	//// おまじない /////
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	/////////////////////
	
	int N,M,K;
	cin>>N>>M>>K;
	vector<vector<vector<int>>> dp(K+1,vector<vector<int>>(N+1,vector<int>(N+1, -1)));
	dp[0][1][N-1]=0;
	for(int d=0;d<K;d++){
		for(int p=1;p<=N-1;p++){
			for(int r=1;r<=N;r++){
				if(dp[d][p][r]==-1) continue;
				for(int c=1;c<=r;c++){
					dp[d+1][c][r-c]=max(dp[d+1][c][r-c], dp[d][p][r]+p*c+c*(c-1)/2);
				}
			}
		}
	}

	int use=N*(N-1)/2-M;
	vector<int> cnt(K+1);
	cnt[K]=1;
	int m=-1;
	for(int k=1;k<=N;k++){
		if(dp[K][k][0]>m){
			m=dp[K][k][0];
			cnt[K]=k;
		}
	}
	if(use<K || use>m){
		NO;
	}
	else{
		YES;
		int cons=0;
		for(int k=K;k>0;k--){
			int t=cnt[k];
			for(int j=1;j+cons+t<=N;j++){
				if(dp[k-1][j][cons+t]>-1 && dp[k-1][j][cons+t]==dp[k][t][cons]-j*t-t*(t-1)/2){
					cnt[k-1]=j;
				}
			}
			cons+=t;
		}

		vector<vector<int>> list(K+1);
		int now=0;
		rep(i,K+1){
			rep(j,cnt[i]){
				list[i].push_back(now);
				now++;
			}
		}
		vector<vector<int>> prio(N), hori(N);
		rep(i,K){
			rep(j,cnt[i]){
				int now=list[i][j];
				for(int x:list[i+1]){
					prio[now].push_back(x);
				}
				for(int x:list[i]){
					if(x!=now){
						hori[now].push_back(x);
					}
				}
			}
		}
		rep(i,N){
			rsort(prio[i]);
		}
		int det=0;
		vector<vector<bool>> connect(N,vector<bool>(N,false));
		function<void(int)> dfs=[&](int now){
			if(det==use) return;
			for(int x:prio[now]){
				if(!connect[now][x]){
					connect[now][x]=true;
					connect[x][now]=true;
					det++;
					dfs(x);
				}
				if(det==use) return;
			}
			for(int x:hori[now]){
				if(!connect[now][x]){
					connect[now][x]=true;
					connect[x][now]=true;
					det++;
					dfs(x);
				}
				if(det==use) return;
			}
		};
		dfs(0);
		rep(i,N){
			for(int j=i+1;j<N;j++){
				if(!connect[i][j]){
					cout<<i+1<<" "<<j+1<<"\n";
				}
			}
		}
	}
}