QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#115615#6629. Travelling TraderMr_Eight21 134ms59252kbC++1412.4kb2023-06-26 13:13:522023-06-26 13:13:56

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-26 13:13:56]
  • 评测
  • 测评结果:21
  • 用时:134ms
  • 内存:59252kb
  • [2023-06-26 13:13:52]
  • 提交

answer

//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <functional>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
#define int long long
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define itn int
#define nit int
#define ll long long
#define ms multiset
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define re register
#define ri re int
#define il inline
#define pii pair<int,int>
#define cp complex<double>
#define vi vector<int>
#define ull unsigned long long
#define mem0(x) memset(x,0,sizeof(x))
#define mem0x3f(x) memset(x,0x3f,sizeof(x))
using namespace std;
using std::bitset;
//using namespace __gnu_pbds;
const double Pi=acos(-1);
namespace fastIO {
	template<class T>
	inline void read(T &x) {
		x=0;
		bool fu=0;
		char ch=0;
		while(ch>'9'||ch<'0') {
			ch=getchar();
			if(ch=='-')fu=1;
		}
		while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
		if(fu)x=-x;
	}
	inline int read() {
		int x=0;
		bool fu=0;
		char ch=0;
		while(ch>'9'||ch<'0') {
			ch=getchar();
			if(ch=='-')fu=1;
		}
		while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
		return fu?-x:x;
	}
	template<class T,class... Args>
	inline void read(T& t,Args&... args) {
		read(t);
		read(args...);
	}
	char _n_u_m_[40];
	template<class T>
	inline void write(T x) {
		if(x==0) {
			putchar('0');
			return;
		}
		T tmp = x > 0 ? x : -x ;
		if( x < 0 ) putchar('-') ;
		register int cnt = 0 ;
		while( tmp > 0 ) {
			_n_u_m_[ cnt ++ ] = tmp % 10 + '0' ;
			tmp /= 10 ;
		}
		while( cnt > 0 ) putchar(_n_u_m_[ -- cnt ]) ;
	}
	template<class T>
	inline void write(T x,char ch) {
		write(x);
		putchar(ch);
	}
}
using namespace fastIO;
int n,k,f[200002],h[200002],p[200002],v[200002],fa[200002];
bool vis[200002];
pii mmax[200002],sec[200002];
pair<int,pii >ans;
vector<pii >g[200002];
vector<int>q;
inline void dfs(int pos,int lst) {
	fa[pos]=lst;
	mmax[pos]=sec[pos]= {v[pos],pos};
	for(pii i:g[pos])if(i.first!=lst) {
			dfs(i.first,pos);
			mmax[i.first].first+=i.second+v[pos];
			if(mmax[pos]<mmax[i.first])sec[pos]=mmax[pos],mmax[pos]=mmax[i.first];
			else sec[pos]=max(sec[pos],mmax[i.first]);
		}
}
inline void D(int pos,int res) {
	q.push_back(pos);
	vis[pos]=true;
	if(res!=1)for(auto i:g[pos])if(!vis[i.first])D(i.first,res-1);
}
inline void solve(int pos) {
	if(pos!=1)solve(fa[pos]);
	D(pos,k);
}
inline void play(int pos,int lst) {
	write(pos,' ');
	for(pii i:g[pos])if(i.first!=lst) {
			for(pii j:g[i.first])if(j.first!=pos)play(j.first,i.first);
			write(i.first,' ');
		}
}
int root=1;
namespace K {
	vector<int>g[200002];
	int I[200002],O[200002],P[200002],X[200002],ii[200002],xx[200002];
	inline void dfs(int pos,int lst) {
		I[pos]=O[pos]=P[pos]=X[pos]=p[pos];
		if(g[pos].size()==1&&g[pos][0]==lst)return;
		for(int i:g[pos])if(i!=lst)dfs(i,pos);
		int bp=0,bi=0,bo=0,bx=0;
		for(int i:g[pos])if(i!=lst) {
				if(!bp||P[bp]-p[bp]<P[i]-p[i])bp=i;
				if(!bi||I[bi]-p[bi]<I[i]-p[i])bi=i;
				if(!bo||O[bo]-p[bo]<O[i]-p[i])bo=i;
				if(!bx||X[bx]-p[bx]<X[i]-p[i])bx=i;
			}
		I[pos]=O[pos]=P[pos]=X[pos]=0;
		for(int i:g[pos])if(i!=lst) {
				if(i!=bp)I[pos]=max(I[pos],P[bp]-p[bp]+I[i]-p[i]);
				if(i!=bi)I[pos]=max(I[pos],P[i]-p[i]+I[bi]-p[bi]);
			}
		for(int i:g[pos])if(i!=lst) {
				if(i!=bo)X[pos]=max(X[pos],O[bo]-p[bo]+X[i]-p[i]);
				if(i!=bx)X[pos]=max(X[pos],O[i]-p[i]+X[bx]-p[bx]);
			}
		xx[pos]=X[pos];
		if(g[pos].size()+(pos==root)>=4) {

			int to=0,tp=0,ti=0;
			int ao=0,ap=0,ai=0;
			int res=-1;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!to||O[to]-p[to]<O[i]-p[i]))to=i;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!tp||P[tp]-p[tp]<P[i]-p[i]))tp=i;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!ti||I[ti]-p[ti]<I[i]-p[i]))ti=i;
			if(O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti]>res)res=O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti],ao=to,ap=tp,ai=ti;
			to=0,tp=0,ti=0;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!to||O[to]-p[to]<O[i]-p[i]))to=i;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!ti||I[ti]-p[ti]<I[i]-p[i]))ti=i;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!tp||P[tp]-p[tp]<P[i]-p[i]))tp=i;
			if(O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti]>res)res=O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti],ao=to,ap=tp,ai=ti;
			to=0,tp=0,ti=0;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!ti||I[ti]-p[ti]<I[i]-p[i]))ti=i;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!to||O[to]-p[to]<O[i]-p[i]))to=i;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!tp||P[tp]-p[tp]<P[i]-p[i]))tp=i;
			if(O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti]>res)res=O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti],ao=to,ap=tp,ai=ti;
			to=0,tp=0,ti=0;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!ti||I[ti]-p[ti]<I[i]-p[i]))ti=i;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!tp||P[tp]-p[tp]<P[i]-p[i]))tp=i;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!to||O[to]-p[to]<O[i]-p[i]))to=i;
			if(O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti]>res)res=O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti],ao=to,ap=tp,ai=ti;
			to=0,tp=0,ti=0;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!tp||P[tp]-p[tp]<P[i]-p[i]))tp=i;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!ti||I[ti]-p[ti]<I[i]-p[i]))ti=i;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!to||O[to]-p[to]<O[i]-p[i]))to=i;
			if(O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti]>res)res=O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti],ao=to,ap=tp,ai=ti;
			to=0,tp=0,ti=0;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!tp||P[tp]-p[tp]<P[i]-p[i]))tp=i;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!to||O[to]-p[to]<O[i]-p[i]))to=i;
			for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!ti||I[ti]-p[ti]<I[i]-p[i]))ti=i;
			if(O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti]>res)res=O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti],ao=to,ap=tp,ai=ti;
			X[pos]=max(X[pos],res);
		}
		if(xx[pos]!=X[pos])xx[pos]=-1;

		O[pos]=P[bp]-p[bp],P[pos]=O[bo]-p[bo];
		I[pos]+=p[pos],O[pos]+=p[pos],P[pos]+=p[pos],X[pos]+=p[pos];
		for(int i:g[pos])if(i!=lst) {
				I[pos]+=p[i],O[pos]+=p[i],P[pos]+=p[i],X[pos]+=p[i];
			}
		ii[pos]=I[pos];
		for(int i:g[pos])if(i!=lst)I[pos]=max(I[pos],p[pos]+X[i]);
		X[pos]=max(X[pos],I[pos]);
		if(xx[pos]==-1)xx[pos]=0;
		else xx[pos]=1;
	}
	vector<int>ans;
	inline void solve(int pos,int lst,char tp) { //if(pos==0)while(true);
		if(g[pos].size()==1&&g[pos][0]==lst) {
			ans.push_back(pos);
			return;
		}
		int bp=0,bi=0,bo=0,bx=0;
		for(int i:g[pos])if(i!=lst) {
				if(!bp||P[bp]-p[bp]<P[i]-p[i])bp=i;
				if(!bi||I[bi]-p[bi]<I[i]-p[i])bi=i;
				if(!bo||O[bo]-p[bo]<O[i]-p[i])bo=i;
				if(!bx||X[bx]-p[bx]<X[i]-p[i])bx=i;
			}//cerr<<bp<<" "<<bi<<" "<<bo<<endl;
		if(tp=='I') {
			ans.push_back(pos);
			int x=0,y=0,II=-1;
			for(int i:g[pos])if(i!=lst) {
					if(i!=bp&&II<P[bp]-p[bp]+I[i]-p[i])II=P[bp]-p[bp]+I[i]-p[i],x=bp,y=i;
					if(i!=bi&&II<P[i]-p[i]+I[bi]-p[bi])II=P[i]-p[i]+I[bi]-p[bi],x=i,y=bi;
				}
			for(int k:g[pos])if(k!=lst)II+=p[k];
			if(II+p[pos]==I[pos]) {//cerr<<x<<" "<<y<<endl;
				solve(x,pos,'P');
				for(int i:g[pos])if(i!=x&&i!=y&&i!=lst)ans.push_back(i);
				solve(y,pos,'I');
				return;
			}
			for(int i:g[pos])if(i!=lst&&I[pos]==p[pos]+X[i]) { //cerr<<"K"<<pos<<endl;
					solve(i,pos,'X');
					return;
				}
		} else if(tp=='P') {
			for(int i:g[pos])if(i!=bo&&i!=lst)ans.push_back(i);
			solve(bo,pos,'O');
			ans.push_back(pos);
		} else if(tp=='O') {
			ans.push_back(pos);
			solve(bp,pos,'P');
			for(int i:g[pos])if(i!=bp&&i!=lst)ans.push_back(i);
		} else if(tp=='X') {cerr<<pos<<" "<<X[pos]<<" "<<I[pos]<<endl;
			if(X[pos]==I[pos]) {
				solve(pos,lst,'I');
				return;
			}
			int x=0,y=0,XX=-1;
			for(int i:g[pos])if(i!=lst) {
					if(i!=bo&&XX<O[bo]-p[bo]+X[i]-p[i])XX=O[bo]-p[bo]+X[i]-p[i],x=bo,y=i;
					if(i!=bx&&XX<O[i]-p[i]+X[bx]-p[bx])XX=O[i]-p[i]+X[bx]-p[bx],x=i,y=bx;
				}
			if(xx[pos]) { //cerr<<"K";
				for(int i:g[pos])if(i!=x&&i!=y&&i!=lst)ans.push_back(i);
				solve(x,pos,'O');
				ans.push_back(pos);
				solve(y,pos,'X');
			} else {
				int to=0,tp=0,ti=0;
				int ao=0,ap=0,ai=0;
				int res=-1;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!to||O[to]-p[to]<O[i]-p[i]))to=i;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!tp||P[tp]-p[tp]<P[i]-p[i]))tp=i;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!ti||I[ti]-p[ti]<I[i]-p[i]))ti=i;
				if(O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti]>res)res=O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti],ao=to,ap=tp,ai=ti;
				to=0,tp=0,ti=0;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!to||O[to]-p[to]<O[i]-p[i]))to=i;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!ti||I[ti]-p[ti]<I[i]-p[i]))ti=i;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!tp||P[tp]-p[tp]<P[i]-p[i]))tp=i;
				if(O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti]>res)res=O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti],ao=to,ap=tp,ai=ti;
				to=0,tp=0,ti=0;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!ti||I[ti]-p[ti]<I[i]-p[i]))ti=i;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!to||O[to]-p[to]<O[i]-p[i]))to=i;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!tp||P[tp]-p[tp]<P[i]-p[i]))tp=i;
				if(O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti]>res)res=O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti],ao=to,ap=tp,ai=ti;
				to=0,tp=0,ti=0;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!ti||I[ti]-p[ti]<I[i]-p[i]))ti=i;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!tp||P[tp]-p[tp]<P[i]-p[i]))tp=i;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!to||O[to]-p[to]<O[i]-p[i]))to=i;
				if(O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti]>res)res=O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti],ao=to,ap=tp,ai=ti;
				to=0,tp=0,ti=0;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!tp||P[tp]-p[tp]<P[i]-p[i]))tp=i;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!ti||I[ti]-p[ti]<I[i]-p[i]))ti=i;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!to||O[to]-p[to]<O[i]-p[i]))to=i;
				if(O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti]>res)res=O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti],ao=to,ap=tp,ai=ti;
				to=0,tp=0,ti=0;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!tp||P[tp]-p[tp]<P[i]-p[i]))tp=i;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!to||O[to]-p[to]<O[i]-p[i]))to=i;
				for(int i:g[pos])if(i!=lst&&i!=to&&i!=tp&&i!=ti&&(!ti||I[ti]-p[ti]<I[i]-p[i]))ti=i;
				if(O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti]>res)res=O[to]-p[to]+P[tp]-p[tp]+I[ti]-p[ti],ao=to,ap=tp,ai=ti;
				for(int i:g[pos])if(i!=ao&&i!=ap&&i!=ai&&i!=lst)ans.push_back(i);
				solve(ao,pos,'O');
				ans.push_back(pos);
				solve(ap,pos,'P');
				solve(ai,pos,'I');
			}
		}
	}
	void main() {
		dfs(root,0);
		write(I[root],'\n');
		solve(root,0,'I');
		//	ll su=0;for(int i:ans)su+=p[i];if(su!=I[root])while(true);
			//F(i,1,n)if(O[i]!=P[i])while(true);
		write(ans.size(),'\n');
		for(int i:ans)write(i,' ');
	}
	/*
	31 2
	2 1
	3 1
	4 2
	5 2
	6 3
	7 3
	8 4
	9 4
	10 5
	11 5
	12 6
	13 6
	14 7
	15 7
	16 8
	17 8
	18 9
	19 9
	20 10
	21 10
	22 11
	23 11
	24 12
	25 12
	26 13
	27 13
	28 14
	29 14
	30 15
	31 15
	1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
	*/
}
signed main() {
	cin>>n>>k;
	F(i,2,n) {
		int u=read(),v=read();
		g[u].push_back({v,0});
		g[v].push_back({u,0});
		K::g[u].push_back(v);
		K::g[v].push_back(u);
	}
	ll sum=0;
	F(i,1,n)read(p[i]),f[i]=h[i]=p[i],sum+=p[i];
	if(k==2) {
		K::main();
		return 0;
	}
	if(k==3) {
		write(sum,'\n');
		write(n,'\n');
		play(1,0);
	}
	F(pos,1,n)for(pii i:g[pos])f[pos]+=p[i.first];
	F(pos,1,n)for(pii i:g[pos])h[pos]+=f[i.first]-p[pos];
	if(k==1) {
		F(i,1,n)v[i]=p[i];
	} else if(k==2) {
		F(i,1,n)v[i]=f[i];
		F(pos,1,n)for(pii &i:g[pos])i.second=-p[pos]-p[i.first];
	} else if(k==3) {
		F(i,1,n)v[i]=h[i];
		F(pos,1,n)for(pii &i:g[pos])i.second=p[pos]+p[i.first]-f[pos]-f[i.first];
	}
//	F(i,1,n)cerr<<v[i]<<" ";cerr<<endl;
	dfs(1,0);
	if(k==1) {
		cout<<mmax[1].first<<endl;
		for(int i=mmax[1].second; i; i=fa[i])vis[i]=true;
		solve(mmax[1].second);
		write(q.size(),'\n');
		for(auto i:q)write(i,' ');
		return 0;
	}
	return 0;
}

详细

Subtask #1:

score: 2
Accepted

Test #1:

score: 2
Accepted
time: 1ms
memory: 23924kb

input:

2 1
1 2
255959470 961356354

output:

1217315824
2
1 2 

result:

ok correct!

Test #2:

score: 0
Accepted
time: 5ms
memory: 26020kb

input:

1000 1
730 89
762 280
923 523
740 22
679 350
448 769
102 712
154 965
219 32
238 289
484 502
183 311
999 682
806 450
275 101
131 197
749 720
131 937
960 202
503 320
95 262
595 133
809 560
659 451
843 218
258 842
564 316
729 727
413 237
606 531
469 258
612 8
707 539
359 680
957 639
381 708
104 490
234...

output:

95535
17
1 173 449 472 396 545 668 270 981 489 852 836 763 6 218 843 758 

result:

ok correct!

Test #3:

score: 0
Accepted
time: 83ms
memory: 45776kb

input:

200000 1
111811 133538
179217 151840
171974 117009
187613 169656
64662 13136
132434 89348
52802 175565
194821 191312
196047 99457
40339 152969
29669 180026
147677 57771
119598 58048
80707 146623
72232 101624
48109 11800
71536 69
31573 129
24409 17263
1033 148614
66977 149926
138624 87653
141889 1178...

output:

221
35
1 145832 90178 52464 3517 55709 39776 67451 59386 143855 102872 38865 13093 177086 7366 190908 160039 69864 196809 13257 612 171083 182883 14221 93359 52156 27994 103745 151704 138607 5346 14735 29598 89600 128747 

result:

ok correct!

Test #4:

score: 0
Accepted
time: 83ms
memory: 46780kb

input:

200000 1
102636 78442
179388 84484
161437 35179
102313 154299
62439 71542
176361 125315
174129 186376
180886 54947
154823 114239
174647 112385
136495 187134
157035 96260
101101 192444
58209 23947
55494 191600
168007 162648
140149 73180
130665 180633
129328 67380
90262 134914
185905 104220
111321 154...

output:

21795891322
36
1 13557 199188 104317 71891 69787 1221 63258 191536 179446 83510 187880 124824 43888 83237 194602 59080 196038 195977 18490 43421 110298 60011 137785 140692 48345 68279 128780 198550 29394 56331 112092 192199 177180 16418 142142 

result:

ok correct!

Test #5:

score: 0
Accepted
time: 106ms
memory: 45852kb

input:

200000 1
682 75953
92444 160568
113369 93705
154622 193304
149619 128186
104784 48913
131684 161196
25886 151867
89191 19511
99233 137377
104650 120096
64347 93526
111350 71598
7568 120116
123497 76821
25436 190715
99884 33654
109438 69462
165464 2475
163215 34551
33926 85078
101208 193355
50705 828...

output:

99327575017
197
1 178606 82034 53029 10508 21404 203 109187 121716 142023 3901 36728 9916 192913 18250 170199 113960 179753 163922 179588 31797 31645 183321 83207 13973 128176 38001 160968 9055 62809 168173 43933 187373 123795 114656 2192 193151 25062 141855 133596 155793 64049 57320 93903 33957 139...

result:

ok correct!

Test #6:

score: 0
Accepted
time: 88ms
memory: 46232kb

input:

200000 1
91999 92900
195726 58991
132067 99937
168188 152017
188495 19779
105961 45241
53406 75757
85118 170259
46250 47585
132248 8609
195110 32777
164307 95643
133411 739
170952 145623
19297 14414
171045 97619
74663 193421
139543 189434
36319 56453
77520 91164
91469 30021
128798 62259
183807 15271...

output:

9098893435
13
1 164355 56677 150505 174723 115829 88068 105453 199874 190131 165416 182628 114943 

result:

ok correct!

Test #7:

score: 0
Accepted
time: 60ms
memory: 44176kb

input:

200000 1
189797 1
1 148138
1 95067
141831 1
168151 1
1 25692
95612 1
1 135979
1 141581
119622 1
1 131946
86508 1
98799 1
1 189104
1 117526
46338 1
1 166375
1 28026
165221 1
54204 1
1 98743
1 181414
1 34313
1 71302
1 161200
1 146339
1 47014
1 137258
1 57857
1 196493
1 99105
54487 1
104725 1
1 45203
1...

output:

1175349557
2
1 153544 

result:

ok correct!

Test #8:

score: 0
Accepted
time: 65ms
memory: 44892kb

input:

199999 1
56367 178046
1 156890
170478 1
111308 177326
1 188427
1 90169
126610 1
161930 167698
96500 126424
118330 158517
186608 1
95505 107863
1 142887
72279 27494
1 114700
118535 1
68584 63156
97555 19966
39239 1
128030 1
1 86200
66974 1
34616 47100
173578 1
1 117279
89769 43412
1 89670
103573 1
13...

output:

2999144210
3
1 52552 129910 

result:

ok correct!

Test #9:

score: 0
Accepted
time: 104ms
memory: 59252kb

input:

200000 1
95601 67789
174512 65854
198542 123861
153390 92355
141969 168754
177054 101194
25665 15524
131869 168080
171051 30732
97293 119758
103002 59019
141990 124310
161550 116618
2585 170410
132999 38200
99202 98733
73949 155033
144918 64086
1594 34916
37138 165382
13452 170885
136973 62178
15250...

output:

200000000000000
200000
1 47213 179780 132180 145558 41335 179095 156350 24912 104386 94658 54370 97034 108043 73905 141018 157563 199841 176455 147422 87545 190562 135095 24903 62484 36389 156106 45144 120321 4911 173474 102976 13602 68252 7332 141515 59337 182112 124040 38089 15458 161370 41901 144...

result:

ok correct!

Test #10:

score: 0
Accepted
time: 71ms
memory: 54608kb

input:

200000 1
122636 169264
76896 89915
72116 125306
186356 74852
84394 177419
21725 144848
106395 111991
189102 195804
6151 170169
185460 146764
6304 149801
147880 99539
6202 175326
104277 26515
39402 33436
116555 185545
44341 92305
197925 125286
28215 102176
182103 160554
105237 169007
105618 75618
190...

output:

49951940813408
100001
1 88700 18534 14218 21693 84470 150823 121376 192964 139616 11067 93019 188349 55336 13628 87630 31553 28945 29827 140175 179655 10038 38915 99968 89953 72978 102045 45280 176852 171879 100086 93399 183932 84482 111738 112608 136016 101850 19371 96135 54333 95939 2865 140685 13...

result:

ok correct!

Test #11:

score: 0
Accepted
time: 39ms
memory: 47832kb

input:

200000 1
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54...

output:

13954593167
18
1 2 5 10 20 40 80 161 323 647 1295 2590 5181 10363 20727 41454 82908 165817 

result:

ok correct!

Subtask #2:

score: 7
Accepted

Test #12:

score: 7
Accepted
time: 5ms
memory: 25928kb

input:

2 2
2 1
243296356 635616793

output:

878913149
2
1 2 

result:

ok correct!

Test #13:

score: 0
Accepted
time: 1ms
memory: 26096kb

input:

10 2
6 4
3 7
5 10
6 10
8 2
3 9
3 5
4 2
1 4
2 4 2 5 5 4 2 3 4 2

output:

33
10
1 4 10 3 7 9 5 6 2 8 

result:

ok correct!

Test #14:

score: 0
Accepted
time: 1ms
memory: 25956kb

input:

200 2
150 170
21 33
96 152
143 26
136 70
92 159
34 164
163 182
74 115
93 61
151 83
81 119
10 146
114 170
39 83
139 4
173 41
193 96
87 57
14 164
107 51
45 15
157 17
43 183
96 30
11 137
55 18
138 81
87 12
112 122
159 82
195 185
75 71
16 191
33 88
70 195
149 114
106 160
96 118
92 44
9 141
107 143
151 2...

output:

57921623677
100
1 135 89 194 179 151 39 83 27 112 40 125 180 120 117 122 99 72 33 96 105 131 114 171 28 110 149 170 59 193 21 88 162 94 138 45 129 25 78 62 199 36 127 15 12 53 70 76 159 44 24 178 17 41 67 173 186 42 116 92 82 197 101 5 32 121 87 29 198 64 93 19 141 8 126 37 100 3 9 108 52 61 54 14 1...

result:

ok correct!

Test #15:

score: 0
Accepted
time: 0ms
memory: 28168kb

input:

200 2
33 5
171 115
70 64
38 42
123 154
167 183
152 177
36 102
98 116
125 187
61 148
143 136
62 169
102 142
86 189
115 100
85 172
136 50
158 113
133 5
10 108
90 178
90 21
127 28
122 189
115 18
83 109
197 11
53 70
191 141
166 90
70 9
74 148
160 7
186 151
197 86
147 82
107 161
122 140
110 58
179 25
107...

output:

47106979559
87
1 7 51 111 130 67 160 52 189 62 48 127 126 138 20 70 65 156 9 64 53 80 36 196 155 76 110 135 193 175 177 78 24 5 133 33 149 152 58 13 184 106 117 119 191 154 88 73 139 174 59 4 27 170 123 141 120 167 145 34 50 146 15 143 136 183 39 108 118 10 129 37 115 95 66 100 171 71 165 18 151 147...

result:

ok correct!

Test #16:

score: 0
Accepted
time: 0ms
memory: 26008kb

input:

200 2
139 197
14 69
160 138
115 60
1 141
176 33
94 88
108 26
106 20
96 60
126 180
171 110
140 91
138 63
57 183
42 62
126 163
126 64
87 167
22 142
190 112
27 120
187 109
83 111
23 196
95 47
105 177
96 170
192 113
136 188
24 198
116 137
53 177
178 38
30 158
125 64
123 132
36 114
77 192
125 165
194 7
9...

output:

73032451334
133
1 141 7 50 194 75 65 53 124 105 177 139 122 134 46 16 197 14 114 83 99 193 120 67 22 70 175 51 32 101 107 36 91 146 189 43 90 15 191 95 144 172 73 174 45 167 87 159 81 109 4 25 140 2 199 198 60 170 82 42 121 157 78 184 155 182 62 186 54 96 24 158 165 3 136 127 10 17 143 39 188 149 12...

result:

ok correct!

Test #17:

score: 0
Accepted
time: 1ms
memory: 27940kb

input:

200 2
182 43
15 179
37 173
45 38
62 4
131 151
83 188
84 58
183 148
155 59
141 133
128 19
191 170
129 87
67 156
120 199
94 11
162 27
175 86
73 50
143 94
81 103
84 120
12 19
59 38
48 34
127 41
196 87
135 69
43 119
54 176
180 112
89 60
67 117
149 18
53 61
12 1
46 67
25 38
8 52
119 51
162 197
12 31
166 ...

output:

63859058076
111
1 31 12 30 158 19 189 180 29 36 112 85 66 124 128 45 25 3 18 69 151 59 179 15 5 155 171 65 33 7 38 181 4 187 22 144 140 91 54 192 111 26 184 136 165 191 120 58 70 84 170 118 56 196 90 122 182 119 63 167 64 160 88 80 51 43 93 8 76 123 60 87 57 20 83 47 94 44 163 132 95 143 11 127 129 ...

result:

ok correct!

Test #18:

score: 0
Accepted
time: 3ms
memory: 26012kb

input:

200 2
12 76
61 106
151 109
163 180
11 135
109 179
35 199
86 104
82 109
80 70
15 123
180 154
134 91
187 81
167 4
27 71
174 101
124 127
154 29
173 175
172 61
59 109
53 55
76 55
174 67
50 169
180 32
1 182
126 3
148 146
58 127
26 181
189 47
10 156
120 112
157 149
136 166
146 122
59 17
99 136
55 138
49 1...

output:

59693686065
120
1 186 116 108 104 86 183 58 102 87 47 146 177 148 122 60 190 189 46 57 5 79 163 32 2 154 119 29 180 98 178 176 14 192 101 120 114 107 169 97 25 50 196 112 44 88 48 197 76 138 158 24 53 159 41 55 156 143 128 59 74 164 139 28 9 65 89 135 155 142 51 167 18 90 100 16 38 4 42 11 199 36 92...

result:

ok correct!

Test #19:

score: 0
Accepted
time: 0ms
memory: 26032kb

input:

200 2
33 83
16 197
177 12
71 47
85 60
34 49
96 78
30 39
63 122
95 17
168 74
89 83
62 134
45 166
48 6
178 91
151 72
153 47
104 174
86 140
33 134
24 51
129 71
48 94
141 93
64 118
155 50
43 28
182 92
31 142
105 56
156 100
83 69
179 90
140 127
186 148
16 47
175 4
123 173
27 50
154 186
107 98
200 20
66 6...

output:

61122293114
124
1 173 123 101 27 152 155 55 50 190 6 11 195 94 165 149 180 71 153 59 16 102 125 58 163 126 197 47 111 172 48 122 181 68 26 37 187 96 22 135 65 124 41 53 88 63 174 104 15 106 28 52 85 113 107 75 31 12 151 185 72 44 13 42 177 90 98 60 21 43 116 87 103 112 69 89 33 139 14 8 20 67 196 16...

result:

ok correct!

Test #20:

score: 0
Accepted
time: 1ms
memory: 25888kb

input:

200 2
91 28
137 24
181 33
82 19
90 182
180 77
2 6
190 176
100 181
13 140
52 77
85 189
28 29
176 22
7 180
55 176
99 113
6 93
28 51
117 44
180 127
114 174
102 92
13 14
129 181
80 24
95 28
181 195
162 4
28 188
55 162
59 131
47 45
145 176
136 197
145 57
159 117
143 106
192 106
126 28
43 23
51 73
109 28
...

output:

48771917800
98
1 91 29 51 95 188 109 64 79 126 135 21 166 113 99 26 46 36 130 40 104 103 28 190 22 55 145 97 12 117 11 133 62 13 63 172 198 93 102 81 84 65 17 30 59 131 37 92 6 24 151 136 8 176 82 90 160 155 69 158 106 50 125 143 192 49 165 19 129 48 23 43 181 25 96 199 132 67 41 78 71 180 184 154 1...

result:

ok correct!

Test #21:

score: 0
Accepted
time: 1ms
memory: 26016kb

input:

200 2
117 30
120 159
129 100
29 57
57 71
96 72
53 153
171 96
138 197
13 72
142 74
64 85
148 150
145 106
190 23
198 177
58 127
163 67
32 183
26 155
94 159
170 70
12 181
13 24
157 116
163 40
126 76
195 193
92 9
4 113
196 135
196 154
110 56
79 196
50 14
68 46
143 36
131 50
46 2
179 160
92 31
61 3
169 9...

output:

70064073402
147
1 197 18 165 6 168 98 180 136 122 47 121 167 103 48 138 123 104 163 73 162 81 67 21 161 174 189 119 145 170 16 193 93 175 141 8 76 63 34 159 105 44 143 172 65 36 82 94 200 126 137 155 195 70 75 106 85 43 91 190 133 148 97 41 125 56 110 111 150 160 140 23 64 37 144 100 128 7 182 157 1...

result:

ok correct!

Test #22:

score: 0
Accepted
time: 3ms
memory: 26172kb

input:

200 2
29 106
175 25
175 87
144 67
51 68
118 71
184 165
74 86
127 64
12 68
180 186
53 164
193 64
144 98
106 122
44 144
178 144
144 94
17 64
106 89
199 1
64 108
28 61
39 199
106 28
23 148
69 106
66 74
164 68
92 185
144 68
78 143
168 126
148 196
72 9
74 160
106 128
63 148
121 178
157 68
72 148
104 144
...

output:

64091222931
110
1 80 84 39 199 67 98 44 178 94 104 31 140 37 96 151 81 143 26 169 134 92 165 111 18 74 16 47 50 103 175 97 115 182 167 64 8 106 172 20 200 65 188 48 71 118 29 122 89 28 69 128 146 3 129 75 190 101 40 158 36 144 51 12 157 145 83 137 82 42 177 112 123 54 141 164 53 5 68 148 73 2 192 90...

result:

ok correct!

Test #23:

score: 0
Accepted
time: 6ms
memory: 26016kb

input:

200 2
161 12
189 84
46 61
69 75
139 170
146 21
162 91
20 125
40 78
152 25
81 140
15 138
39 184
85 183
29 59
166 126
127 24
125 56
94 26
92 37
33 196
168 16
75 64
148 57
112 142
185 46
49 195
76 18
88 79
70 125
194 136
12 154
77 195
10 2
86 155
90 170
83 67
38 179
172 175
198 191
11 51
67 42
25 93
18...

output:

82840243479
163
1 151 57 165 147 148 60 17 97 110 198 121 191 101 143 71 152 134 46 100 33 131 192 116 173 31 185 61 25 52 5 93 99 114 98 43 197 81 144 64 69 12 55 68 174 199 164 133 66 35 180 72 154 161 75 8 39 140 14 188 117 13 19 132 177 85 183 169 80 200 21 146 84 74 79 88 7 182 9 189 37 145 92 ...

result:

ok correct!

Test #24:

score: 0
Accepted
time: 5ms
memory: 26016kb

input:

200 2
19 106
54 55
83 185
106 178
78 194
51 66
133 200
106 58
106 35
163 150
50 104
96 105
124 105
41 66
124 22
54 106
27 93
106 133
196 124
58 83
106 193
124 110
194 165
150 124
194 13
42 149
127 154
121 159
106 26
100 181
124 82
1 80
177 45
69 100
54 189
61 19
70 106
134 175
168 134
6 112
44 100
1...

output:

60321563038
110
1 19 178 58 35 54 133 193 26 70 155 40 138 93 182 12 167 128 98 113 195 180 174 56 84 188 191 114 6 46 45 31 154 100 141 68 36 140 81 161 121 159 181 69 44 145 148 88 190 173 198 152 143 8 158 104 101 87 38 106 165 13 57 111 142 90 116 71 29 10 78 156 194 124 144 153 199 136 117 109 ...

result:

ok correct!

Test #25:

score: 0
Accepted
time: 7ms
memory: 26012kb

input:

200 2
104 32
163 164
138 166
140 114
144 134
193 184
94 25
196 140
119 160
29 34
170 7
175 60
122 185
85 133
9 53
95 89
171 158
34 155
67 32
73 125
167 128
27 48
157 119
105 2
13 142
134 120
71 118
66 117
182 59
156 43
84 91
126 80
55 192
34 68
64 194
131 75
81 151
117 102
145 104
99 4
3 65
91 35
79...

output:

80439812057
153
1 136 65 3 44 109 45 71 4 69 79 99 118 167 128 88 41 165 64 194 14 93 73 163 43 58 156 108 176 62 164 197 49 133 125 178 25 94 182 123 59 115 19 144 89 120 122 126 168 60 7 46 131 184 100 162 158 171 38 26 75 121 170 172 175 188 51 80 103 185 134 189 140 127 57 154 169 8 15 137 147 1...

result:

ok correct!

Test #26:

score: 0
Accepted
time: 3ms
memory: 26168kb

input:

200 2
105 64
190 149
84 15
184 93
52 80
182 129
160 51
108 184
105 167
9 77
61 80
109 84
161 188
121 2
121 20
175 60
80 154
105 88
25 60
88 10
41 123
105 135
99 184
100 98
152 105
1 75
184 199
163 102
63 88
56 184
83 13
101 123
107 50
120 42
8 78
105 45
105 121
184 92
105 129
136 124
123 139
88 19
7...

output:

51611310581
104
1 33 5 75 64 167 88 135 152 45 121 129 57 46 27 147 102 106 198 84 86 161 172 165 141 50 130 127 189 136 159 51 60 80 12 200 176 52 61 154 98 114 67 30 85 31 111 16 128 4 104 17 162 26 8 74 174 97 32 190 105 41 101 139 96 90 155 77 113 185 193 143 177 68 166 181 144 72 14 123 184 40 ...

result:

ok correct!

Test #27:

score: 0
Accepted
time: 3ms
memory: 28140kb

input:

200 2
8 1
1 22
39 1
168 1
136 1
197 1
1 142
1 4
18 1
187 1
1 74
156 1
1 94
118 1
1 86
1 76
30 1
52 1
1 42
144 1
105 1
64 1
1 9
137 1
112 1
101 1
75 1
1 113
1 164
1 29
1 60
1 167
1 135
1 192
196 1
48 1
1 179
170 1
158 1
1 145
47 1
1 98
143 1
184 1
84 1
72 1
20 1
109 1
1 106
1 3
1 79
55 1
1 77
102 1
1...

output:

89576768884
200
1 8 39 168 136 197 142 4 18 187 74 156 94 118 86 76 30 52 42 144 105 64 9 137 112 101 75 113 164 29 60 167 135 192 196 48 179 170 158 145 47 98 143 184 84 72 20 109 106 3 79 55 77 102 126 7 138 175 120 115 17 159 63 161 181 163 6 70 23 176 93 38 173 160 5 125 186 153 26 28 46 189 41 ...

result:

ok correct!

Test #28:

score: 0
Accepted
time: 1ms
memory: 25988kb

input:

199 2
1 106
198 165
176 34
59 39
1 34
151 36
78 85
1 109
48 4
1 13
165 1
73 163
159 126
150 106
1 33
82 103
17 180
1 151
46 87
1 111
195 1
1 164
25 23
135 161
1 107
1 2
11 58
97 1
170 1
71 57
72 157
1 158
1 186
153 1
1 60
29 1
27 52
50 1
162 122
64 1
95 1
1 75
160 142
134 81
77 155
79 1
1 119
30 169...

output:

101902858721
102
1 121 181 106 34 109 13 165 33 151 111 195 164 107 2 97 170 158 186 153 60 29 50 64 95 75 79 119 157 120 132 128 183 77 90 144 35 168 141 83 45 103 184 161 126 171 99 18 48 180 174 163 118 160 78 112 169 96 52 193 134 136 67 140 69 137 20 76 23 89 162 91 190 56 93 125 177 80 84 131 ...

result:

ok correct!

Test #29:

score: 0
Accepted
time: 0ms
memory: 26112kb

input:

197 2
24 1
65 24
129 58
92 96
61 1
42 18
95 3
167 168
147 110
2 172
143 156
115 110
1 67
158 127
99 134
126 89
30 95
85 13
1 149
128 106
81 118
137 100
146 88
105 1
76 105
153 9
96 123
67 49
61 186
1 9
120 46
51 79
79 1
77 195
17 11
117 7
114 106
135 21
59 1
100 122
179 67
158 184
16 83
96 1
191 75
...

output:

55959842378
56
1 78 181 133 23 24 61 67 149 105 9 79 59 96 121 110 10 100 75 126 158 42 143 88 93 188 13 169 16 53 29 167 46 17 108 182 58 7 197 187 2 118 36 99 21 40 106 162 195 90 95 161 32 97 163 107 

result:

ok correct!

Test #30:

score: 0
Accepted
time: 1ms
memory: 26168kb

input:

196 2
83 40
1 26
46 179
44 181
73 123
46 128
150 168
150 151
134 48
91 48
47 79
161 46
114 35
120 35
183 48
47 66
154 69
150 45
74 40
32 63
48 1
22 18
41 26
1 46
78 47
88 40
152 47
191 44
60 46
57 48
67 73
150 38
48 10
126 89
44 23
44 56
31 126
196 150
80 35
46 25
129 32
20 22
75 44
73 145
170 154
2...

output:

26055322292
42
1 129 158 65 54 193 5 8 37 111 2 102 106 189 63 32 26 48 46 154 126 35 22 44 47 73 40 150 168 45 38 196 93 135 98 166 104 15 115 109 124 151 

result:

ok correct!

Test #31:

score: 0
Accepted
time: 3ms
memory: 30236kb

input:

200 2
119 95
47 18
176 194
73 36
90 105
24 29
79 39
53 98
130 111
42 125
158 15
100 60
128 149
76 41
134 1
108 2
94 157
196 43
145 100
11 9
144 175
37 40
5 120
49 117
165 134
158 84
142 51
82 167
157 108
175 161
50 22
177 35
95 118
77 116
33 131
194 27
116 128
189 72
28 192
130 112
26 4
187 121
97 4...

output:

200000000000
200
1 134 165 110 89 187 121 78 61 122 9 11 173 186 56 30 20 74 69 168 6 93 198 12 191 144 175 161 32 79 39 8 27 194 176 113 148 10 52 150 181 124 99 57 73 36 13 88 192 28 23 183 15 158 84 70 71 166 188 151 140 169 98 53 64 139 43 196 50 22 87 54 156 162 109 189 72 199 159 179 25 40 37 ...

result:

ok correct!

Test #32:

score: 0
Accepted
time: 3ms
memory: 28096kb

input:

200 2
7 176
162 197
197 66
22 23
177 157
49 22
65 171
119 124
155 193
15 41
34 105
61 102
126 31
36 195
14 192
173 57
75 4
104 174
141 20
185 123
199 145
18 9
110 200
148 9
90 137
35 19
106 139
150 172
91 47
168 180
104 70
169 200
161 66
129 114
66 118
71 200
160 133
31 196
36 11
195 49
112 51
22 15...

output:

99918618520
200
1 65 102 24 199 183 34 81 137 150 124 68 170 74 73 11 195 198 22 55 188 109 91 159 173 154 19 83 86 129 63 33 139 108 160 100 194 134 193 136 64 187 200 80 111 44 175 141 54 3 31 87 28 78 15 98 12 178 9 69 4 95 104 5 142 128 132 153 14 177 130 39 66 79 162 158 85 48 138 17 30 143 27 ...

result:

ok correct!

Test #33:

score: 0
Accepted
time: 5ms
memory: 26000kb

input:

200 2
108 103
141 45
176 16
96 38
130 106
18 176
61 23
38 22
154 198
83 123
77 52
102 188
133 125
123 116
120 45
164 195
174 48
163 54
74 31
199 175
79 110
137 173
182 153
22 1
65 54
60 16
187 144
45 188
99 152
17 118
64 118
75 163
74 141
181 184
39 175
172 117
118 100
138 164
172 99
52 162
200 80
1...

output:

97817235416
200
1 55 76 3 38 66 112 192 174 61 127 2 99 117 168 40 19 187 78 178 180 47 151 15 200 60 128 160 176 93 90 105 134 108 179 10 133 140 183 98 118 106 104 86 81 87 88 150 25 49 147 42 123 28 119 70 173 153 56 185 142 77 162 53 197 92 91 167 199 39 171 156 154 121 94 89 181 95 190 26 110 1...

result:

ok correct!

Test #34:

score: 0
Accepted
time: 1ms
memory: 26004kb

input:

200 2
185 93
20 134
91 82
108 129
123 164
104 56
146 113
110 5
83 87
106 63
67 199
41 108
114 133
172 99
57 132
46 199
32 45
170 191
123 200
53 141
124 186
44 162
65 159
85 195
196 19
7 134
64 35
88 58
23 28
30 20
76 11
176 167
36 124
88 148
175 29
31 151
128 4
103 171
50 79
71 127
84 8
36 4
175 109...

output:

92546968269
200
1 70 137 78 161 40 147 179 109 33 56 104 175 111 86 29 14 72 153 177 168 197 83 87 73 38 146 113 67 126 65 159 199 66 13 46 16 122 18 62 51 181 80 74 171 125 98 103 188 55 85 195 20 160 6 30 134 116 35 64 7 68 99 172 102 118 71 127 136 101 52 120 157 22 176 167 91 144 48 193 82 156 1...

result:

ok correct!

Test #35:

score: 0
Accepted
time: 1ms
memory: 30092kb

input:

200 2
186 20
197 94
138 143
75 2
6 102
114 98
195 131
151 62
33 77
85 149
158 164
30 38
21 93
177 133
72 188
145 52
68 176
194 57
118 103
91 112
178 81
63 169
31 155
92 133
29 166
99 15
65 75
159 147
79 55
45 23
139 180
38 119
3 75
114 127
117 112
146 161
99 48
37 132
148 193
178 179
71 116
140 11
1...

output:

82875113284
152
1 75 103 118 35 3 64 33 183 150 113 184 46 96 19 182 191 5 157 49 37 132 175 115 84 57 161 86 53 146 119 136 16 141 105 142 38 12 151 62 40 47 30 11 102 6 160 140 27 55 167 120 50 79 83 131 67 90 22 195 130 23 68 176 101 185 61 158 116 71 154 124 156 171 152 56 129 174 92 169 177 123...

result:

ok correct!

Test #36:

score: 0
Accepted
time: 0ms
memory: 26004kb

input:

200 2
140 198
32 90
73 76
75 155
54 65
192 80
60 37
103 28
120 118
87 118
174 30
174 191
156 138
187 47
200 17
106 179
80 2
137 71
18 75
146 80
53 153
128 82
31 89
180 110
36 82
129 186
180 36
125 53
31 94
124 189
133 83
151 94
175 48
172 97
34 74
64 87
157 139
155 9
33 126
90 160
199 48
25 86
156 2...

output:

79408775618
143
1 140 129 143 91 136 186 130 76 62 145 132 158 92 164 53 189 124 194 154 125 68 16 86 25 46 23 141 40 89 94 151 127 152 31 65 190 134 197 147 184 54 38 139 74 34 84 70 66 166 60 83 88 111 183 133 52 174 165 176 56 77 10 55 99 168 13 169 114 135 96 90 200 17 8 182 14 167 48 126 33 50 ...

result:

ok correct!

Test #37:

score: 0
Accepted
time: 2ms
memory: 25988kb

input:

200 2
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
27...

output:

31861270500
55
1 7 6 27 26 107 106 53 52 13 12 3 2 8 9 39 38 153 152 76 77 19 18 4 5 22 23 94 95 190 191 47 46 11 10 40 41 167 166 83 82 20 21 85 84 168 169 42 43 175 174 87 86 172 173 

result:

ok correct!

Test #38:

score: 0
Accepted
time: 0ms
memory: 26108kb

input:

200 2
1 2
1 3
1 4
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
5 14
5 15
5 16
6 17
6 18
6 19
7 20
7 21
7 22
8 23
8 24
8 25
9 26
9 27
9 28
10 29
10 30
10 31
11 32
11 33
11 34
12 35
12 36
12 37
13 38
13 39
13 40
14 41
14 42
14 43
15 44
15 45
15 46
16 47
16 48
16 49
17 50
17 51
17 52
18 53
18 54
18 55
19 56...

output:

26748477707
43
1 11 13 12 105 106 104 35 36 37 4 3 2 18 19 17 153 154 152 51 50 52 6 7 5 47 48 49 146 147 148 16 14 15 135 136 134 45 46 44 131 133 132 

result:

ok correct!

Subtask #3:

score: 3
Accepted

Dependency #2:

100%
Accepted

Test #39:

score: 3
Accepted
time: 5ms
memory: 26188kb

input:

2000 2
1653 466
455 1262
319 394
823 998
1135 313
244 809
563 850
1865 1303
609 1531
302 1084
504 163
1475 1799
534 258
1597 413
1161 330
676 1694
1315 1619
1646 32
1629 161
280 1765
102 877
474 503
1162 491
1182 1505
532 1820
525 1836
1682 808
1026 80
809 1334
1376 1783
401 708
1323 1443
1242 1215
...

output:

176031446963
333
1 1438 239 459 410 1805 937 1479 605 1216 1325 313 1818 198 242 126 423 1142 1101 438 838 467 512 1133 1471 872 375 783 1912 915 1100 1719 435 877 142 1892 334 325 632 457 1411 658 1284 525 482 287 18 374 82 1574 1003 1870 1452 1046 148 1208 338 660 326 1766 1919 652 97 1726 1161 15...

result:

ok correct!

Test #40:

score: 0
Accepted
time: 7ms
memory: 26084kb

input:

2000 2
892 750
281 1593
1698 1268
1500 653
348 1393
1617 797
1044 680
1517 1883
1081 1003
293 948
412 478
1733 690
1785 1377
1902 1304
1674 1565
1350 131
242 573
1778 275
296 1177
1090 1862
1503 1175
1620 207
1441 323
181 449
219 1911
671 1713
606 1360
1558 834
562 1576
1212 1077
257 1606
790 1496
1...

output:

202483759818
403
1 25 186 1506 1577 563 629 762 1100 1452 687 801 381 1190 1638 36 1952 560 1098 1461 108 668 1095 787 1726 1042 1068 915 1569 772 430 1572 552 1384 348 1157 1393 784 1197 553 650 1680 1868 1787 691 1462 1287 1437 1798 1775 897 808 1586 1729 1199 524 999 439 1196 1792 565 1478 1596 9...

result:

ok correct!

Test #41:

score: 0
Accepted
time: 1ms
memory: 26380kb

input:

2000 2
1581 867
670 1948
1286 1189
292 1357
1538 951
691 1646
502 1385
1071 812
482 469
1853 1303
614 774
363 62
506 91
718 951
1327 306
170 23
128 495
1841 263
178 588
271 252
930 1147
552 1150
1550 1584
685 1699
405 1353
1948 510
1632 327
1854 1167
1327 591
112 800
482 305
598 7
922 1645
1737 1811...

output:

184825610246
359
1 172 394 1959 1661 1191 1453 241 1811 1449 415 1773 934 13 1737 1304 59 1621 1152 323 924 670 598 1810 1558 324 936 510 931 158 1860 827 1630 1952 247 805 574 697 1491 1377 1484 1609 1042 336 1595 254 647 1891 1948 1781 86 1041 90 1060 1032 58 3 992 1770 1641 1124 839 1655 45 1711 ...

result:

ok correct!

Test #42:

score: 0
Accepted
time: 4ms
memory: 28248kb

input:

2000 2
1217 1905
1210 453
765 261
1635 1637
1867 1564
1876 1141
1867 283
1093 1385
677 1050
284 1377
228 1393
541 1985
884 242
1714 1304
118 15
1992 1098
449 181
1549 246
84 1198
913 1522
666 1685
1704 263
589 1407
1870 906
1411 561
1252 562
282 17
1137 372
764 1171
1721 172
1990 1755
1231 1948
201 ...

output:

222905521782
416
1 1544 1036 1655 549 1787 1958 1080 830 763 1901 1414 1617 189 561 1647 1290 982 1694 470 1932 1012 695 1411 1371 620 434 602 593 1986 813 257 83 1085 1457 100 1733 1899 1322 1974 1011 1554 1994 970 818 14 1340 1403 5 1213 687 1305 193 1072 1171 372 215 1043 1422 683 141 1970 1511 1...

result:

ok correct!

Test #43:

score: 0
Accepted
time: 2ms
memory: 26200kb

input:

2000 2
989 1552
460 285
670 1653
190 1210
736 941
1555 647
648 363
1500 1908
241 1143
1702 1181
266 1622
409 955
1442 1033
1236 447
194 1312
463 1304
1994 397
835 564
22 982
1214 562
813 1812
1396 783
191 1449
1760 691
103 1289
493 439
333 1401
283 884
1419 832
1561 277
1582 294
1183 925
7 529
191 1...

output:

176264452857
344
1 1542 146 397 680 376 1823 469 1994 1497 527 309 1688 1734 1766 384 618 30 4 742 22 1684 604 982 943 1136 1595 940 1798 1302 959 776 733 1758 1547 143 554 144 685 1723 1333 339 1299 1086 682 353 1166 1517 1783 657 531 343 1594 1241 662 129 96 190 1300 1487 1733 1597 522 510 857 467...

result:

ok correct!

Test #44:

score: 0
Accepted
time: 3ms
memory: 26080kb

input:

2000 2
1900 687
259 1748
582 1542
1844 470
1752 1845
202 37
1206 807
646 269
1687 681
1482 1630
930 446
391 617
1424 1798
1481 1762
820 295
1263 1766
474 210
372 1407
117 1854
199 216
1779 789
937 555
1494 1909
1824 1319
1001 1938
144 45
785 196
1135 636
390 1866
1404 206
1790 524
1734 663
1604 1767...

output:

362696256044
704
1 1488 461 1747 1736 1234 1316 324 1677 1366 1981 819 1350 448 1561 1149 831 1933 1698 1974 527 796 951 218 1450 869 1398 1069 920 1723 361 911 455 826 1188 1273 1363 1787 519 207 1493 55 1826 1567 1419 629 1646 125 697 1639 85 506 241 1759 862 651 159 1514 372 1964 1407 1572 1466 7...

result:

ok correct!

Test #45:

score: 0
Accepted
time: 1ms
memory: 26364kb

input:

2000 2
284 498
512 963
418 534
206 1186
1506 1397
1511 459
992 742
1644 1013
1474 1397
1942 1941
1673 1229
1384 442
1397 1756
1876 280
2000 1932
1397 1993
1217 1474
1774 1204
737 1785
1356 1384
1473 1116
2000 1812
1617 1739
17 1979
229 1979
723 492
621 227
358 550
206 376
440 1675
1393 1790
909 341
...

output:

203246075730
402
1 532 1248 1778 1610 423 1886 988 1047 1672 1192 104 15 87 437 810 1055 1619 1470 927 140 932 1606 1331 1737 686 362 1811 530 277 477 1004 1239 1467 1608 1009 701 468 1488 847 1961 1648 1142 812 378 454 1255 1084 1771 1638 1048 906 347 440 417 1426 1432 193 1861 487 819 411 108 7 12...

result:

ok correct!

Test #46:

score: 0
Accepted
time: 1ms
memory: 28264kb

input:

2000 2
1237 1826
571 1212
1932 1106
88 1218
764 916
1880 854
700 1803
585 679
891 1587
712 1921
233 738
668 1927
1167 918
432 1789
1377 1585
1344 916
692 1546
1749 1947
1571 1869
1484 1846
1531 1997
694 1957
758 567
1649 181
3 1062
987 1320
533 1487
1402 1085
936 1807
1526 752
183 1513
403 187
1796 ...

output:

404938855945
815
1 1556 348 1319 279 523 727 634 1272 755 175 1938 886 1429 1315 952 1840 1914 1416 1716 1544 287 938 1967 399 1799 370 178 1304 1375 210 364 392 535 1522 1343 1002 339 383 152 1637 812 796 200 613 1311 1793 198 121 1626 442 1043 734 1957 1723 581 911 1452 58 262 887 231 1194 846 258...

result:

ok correct!

Test #47:

score: 0
Accepted
time: 1ms
memory: 26228kb

input:

2000 2
593 1134
610 1128
274 1314
1799 123
1738 1823
523 1117
1272 529
1439 225
1275 450
286 1117
34 365
935 1460
1200 1008
475 1622
854 819
1632 890
996 1743
237 1665
1669 1985
1767 1934
1799 783
12 1601
342 1623
924 144
1269 146
1799 340
1280 1669
1270 1128
950 1245
1686 1730
1117 1202
178 393
180...

output:

273811282141
553
1 627 1219 1386 403 1720 1169 1791 1744 766 1344 1288 1524 1976 1501 968 317 70 729 912 1142 1685 1332 226 641 1018 795 1380 334 573 602 1126 1348 435 1793 1617 129 812 577 903 1162 1051 1559 1748 52 438 199 582 1000 181 493 674 1969 967 592 1337 407 1743 237 1910 1296 225 1439 664 ...

result:

ok correct!

Test #48:

score: 0
Accepted
time: 0ms
memory: 30368kb

input:

2000 2
1383 1
1 1410
1 1106
1154 1
1 1202
1794 1
1512 1
1744 1
221 1
1 917
1637 1
1 118
1 423
164 1
1 1881
479 1
1 1029
1 567
1 193
1 1364
1 45
1458 1
692 1
1765 1
807 1
897 1
43 1
1243 1
1 681
1272 1
1 579
122 1
1 1241
1299 1
1558 1
1 88
726 1
1 654
1900 1
1895 1
1 384
1 661
223 1
1 956
1 1112
38 1...

output:

981828873758
2000
1 1383 1106 1154 1202 1794 1512 1744 221 917 1637 118 423 164 1881 479 1029 567 193 1364 45 1458 692 1765 807 897 43 1243 681 1272 579 122 1241 1299 1558 88 726 654 1900 1895 384 661 223 956 1112 38 1213 1492 1768 969 633 418 172 769 375 558 1620 196 1704 178 1057 1692 313 853 1162...

result:

ok correct!

Test #49:

score: 0
Accepted
time: 5ms
memory: 26312kb

input:

1999 2
1 1197
761 1416
1 1777
1341 30
1 791
966 1025
1 890
1103 1
1195 1929
342 1
219 1
993 553
1 1308
392 726
993 1
1747 777
840 1
1 1977
916 1
1 8
1 447
1125 1740
493 1153
781 762
1 435
1 1939
1965 1030
1 812
1 1962
162 1568
793 82
1208 1087
938 1
1 1512
480 1361
1 957
636 816
56 1585
1 822
1018 1...

output:

1001116296577
1002
1 289 1322 1197 1777 791 890 1103 342 219 1308 993 840 1977 916 8 447 435 1939 812 1962 938 1512 957 822 1018 1700 539 694 430 1803 648 457 1202 792 318 222 1622 1140 1261 1670 141 1052 132 381 1282 476 613 464 462 731 102 405 181 850 971 966 1677 1005 1705 249 1524 1895 1298 1435...

result:

ok correct!

Test #50:

score: 0
Accepted
time: 1ms
memory: 28236kb

input:

1997 2
1471 500
206 950
1847 634
897 1
1227 1
435 1540
1020 5
1058 1810
888 1947
1504 1339
1899 986
1647 1604
1 1836
997 261
1349 1153
965 1
429 1
4 1133
1154 259
1993 1
1760 609
8 1
1 1639
1114 1901
1888 971
969 706
1910 875
1561 1888
1118 40
1 372
860 1849
1 1784
1 330
1521 1951
1354 6
1798 375
12...

output:

505561828143
506
1 1648 841 1570 776 897 1227 1836 965 429 1993 8 1639 372 1784 330 1205 1937 303 1720 1138 1069 1011 342 1431 1244 976 1663 451 1875 915 1974 690 215 1812 1175 442 1066 1470 997 594 1644 1277 1504 1641 634 1763 766 98 138 1828 410 1493 859 1319 546 1581 1206 1073 1108 1085 1302 547 ...

result:

ok correct!

Test #51:

score: 0
Accepted
time: 4ms
memory: 26356kb

input:

1936 2
91 782
1865 1244
427 448
1608 1299
1644 880
5 1509
232 1110
1515 1927
1257 448
1217 1331
1 363
1131 1217
1849 1608
1928 249
482 1384
445 682
274 1075
1283 508
1515 1189
1250 1588
529 1158
1833 1217
1064 968
1746 948
264 1509
1369 92
1865 1395
1369 1312
969 1109
1895 333
955 682
1291 275
1369 ...

output:

72540612666
132
1 955 1659 1300 1742 1884 536 904 1205 1400 1620 701 941 793 1560 1867 673 135 961 1816 219 1118 1005 1581 1346 1022 1734 248 1281 1224 1219 1910 276 1516 420 1016 1520 905 1344 1387 145 1241 778 1500 445 682 363 232 968 1202 621 679 1509 428 1369 1217 1928 91 76 1746 1644 747 320 90...

result:

ok correct!

Test #52:

score: 0
Accepted
time: 5ms
memory: 28832kb

input:

2000 2
1142 984
741 1666
929 727
870 1390
111 797
486 816
974 1047
1836 1891
1942 1457
1730 1121
784 1586
881 1069
809 1611
1749 1483
269 1298
1435 1988
59 549
1663 1161
526 1785
445 1934
1604 562
1494 1070
334 332
1028 723
574 1933
1676 1670
1316 1613
1055 490
1321 1549
1374 83
23 497
796 210
728 1...

output:

2000000000000
2000
1 898 163 862 1352 1782 1563 156 1614 1132 788 356 48 7 1167 1084 921 142 1378 1800 634 1490 1514 855 286 387 1743 1569 998 319 1749 1483 1181 1515 1784 1253 540 1973 650 1862 1144 228 1892 939 216 71 764 725 1876 265 192 1986 1954 868 1416 1387 574 1933 1596 950 1909 16 58 1852 1...

result:

ok correct!

Test #53:

score: 0
Accepted
time: 3ms
memory: 28324kb

input:

2000 2
450 1099
1291 492
1509 508
1606 702
1878 729
1405 58
430 1790
829 737
1424 1560
488 1944
1366 1611
128 607
1935 477
1364 1359
1964 578
471 1112
995 420
405 340
1058 1297
526 1263
527 1557
512 1599
1012 1340
1776 558
1202 1515
1835 277
1219 1610
898 116
625 1123
232 1492
1780 71
722 1280
177 6...

output:

1010476018711
2000
1 555 654 1537 679 404 1178 1167 1651 1974 572 1176 1984 297 997 1995 1823 800 1012 1285 239 347 1813 9 624 1181 1997 1640 1989 633 525 370 362 1793 14 500 1905 728 663 1159 1407 688 291 1664 1397 1476 428 863 1504 887 1264 1312 1105 1637 701 1797 1654 604 644 1297 1046 462 504 12...

result:

ok correct!

Test #54:

score: 0
Accepted
time: 2ms
memory: 26344kb

input:

2000 2
1280 733
1348 842
180 1085
492 865
1924 698
646 249
1106 232
1819 1637
1785 585
673 460
799 1613
955 1512
781 1331
1926 699
518 1314
240 433
1217 346
1819 628
140 1858
1910 854
588 1031
231 582
718 230
1600 1880
1304 471
655 1330
1817 1233
1297 304
1466 113
518 465
14 141
1653 506
31 1557
199...

output:

994437083657
2000
1 1310 725 54 1698 658 874 329 722 357 275 1481 36 1928 644 182 1221 201 1302 1293 757 297 1681 1838 1649 1231 903 1395 1431 1739 846 954 1864 927 1066 607 1165 1351 1963 1647 1144 1579 525 1753 401 1245 1938 853 966 1316 84 1372 1592 1463 1063 1498 1472 489 1972 1038 72 1562 1220 ...

result:

ok correct!

Test #55:

score: 0
Accepted
time: 4ms
memory: 26196kb

input:

2000 2
1033 409
609 267
1734 507
588 1257
112 1620
844 1436
25 599
36 324
583 163
922 286
67 268
1767 720
961 1569
553 239
99 1795
1391 1138
689 1452
1250 953
1260 1794
251 1788
1891 1726
1414 77
689 810
42 389
1688 1957
1799 892
798 1790
612 927
999 582
566 879
1603 741
1153 1356
1998 1288
1993 151...

output:

1011568611012
2000
1 573 690 1630 29 1069 1308 271 1605 223 1388 957 1513 826 1223 1700 672 1158 59 1682 495 576 1015 900 1787 858 1245 366 1001 1741 217 33 1797 1397 219 1471 444 438 1731 1501 911 776 1808 1295 1572 944 1085 1186 708 1286 65 1109 553 1067 1739 239 297 959 1892 542 1565 1494 979 112...

result:

ok correct!

Test #56:

score: 0
Accepted
time: 3ms
memory: 26304kb

input:

2000 2
1213 910
748 565
244 1508
69 1383
1066 1452
1470 20
953 273
926 226
1647 1709
378 1921
1809 1976
1714 1640
1273 1888
1243 591
1277 1937
416 491
1360 367
242 131
819 192
307 1792
1497 317
1710 1547
129 55
457 1380
1046 1331
1397 954
740 1994
1388 1649
819 312
1168 694
713 914
1917 928
979 1671...

output:

804671840202
1502
1 95 1136 400 1846 1915 98 1029 335 1576 1756 511 102 865 1265 1997 1363 589 345 850 1285 343 464 190 719 352 434 1808 383 1909 695 172 414 704 985 1863 1347 487 249 1204 1045 948 1836 851 1542 1405 558 217 1875 1792 1337 1231 135 488 219 587 1717 1676 1642 947 1381 933 372 89 974 ...

result:

ok correct!

Test #57:

score: 0
Accepted
time: 3ms
memory: 26232kb

input:

2000 2
583 1761
646 880
265 1017
669 1241
1606 1517
1791 1712
1199 1024
1939 161
1888 1095
1127 1892
169 1741
1411 627
1932 709
201 1642
1695 1359
1853 34
1597 1117
1629 907
392 1684
247 32
75 1518
1990 1150
1465 878
304 186
288 432
49 1221
406 1738
99 191
1125 1264
903 1572
1493 1804
1783 1402
645 ...

output:

771091486166
1403
1 656 91 1748 1340 1915 723 736 812 1804 1493 999 1826 672 1710 275 98 1833 1490 1368 31 1255 1990 172 1752 1737 842 1225 1741 444 1296 248 594 674 1980 169 331 1437 847 721 182 1104 1089 188 36 1859 1196 852 1170 668 1888 1402 1783 329 1438 1095 308 910 1439 1943 18 437 1295 1775 ...

result:

ok correct!

Test #58:

score: 0
Accepted
time: 4ms
memory: 26312kb

input:

2000 2
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
2...

output:

73323472678
111
1 4 5 20 21 85 84 339 338 1355 1354 677 676 169 168 42 43 10 11 2 3 14 15 61 60 243 242 968 969 1938 1939 484 485 121 120 30 31 7 6 26 27 111 110 441 440 1763 1762 881 880 220 221 55 54 13 12 50 51 207 206 825 824 1648 1649 412 413 103 102 25 24 97 96 387 386 1547 1546 773 772 193 19...

result:

ok correct!

Test #59:

score: 0
Accepted
time: 1ms
memory: 26152kb

input:

2000 2
1 2
1 3
1 4
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
5 14
5 15
5 16
6 17
6 18
6 19
7 20
7 21
7 22
8 23
8 24
8 25
9 26
9 27
9 28
10 29
10 30
10 31
11 32
11 33
11 34
12 35
12 36
12 37
13 38
13 39
13 40
14 41
14 42
14 43
15 44
15 45
15 46
16 47
16 48
16 49
17 50
17 51
17 52
18 53
18 54
18 55
19 5...

output:

50545980022
85
1 9 10 8 75 76 74 666 667 665 1994 1995 1996 222 221 223 25 23 24 3 4 2 20 22 21 188 189 190 1713 1714 1712 571 569 570 63 62 64 7 6 5 44 46 45 401 403 402 1205 1206 1207 134 135 136 15 14 16 141 142 140 1257 1258 1256 419 420 421 47 48 49 437 439 438 1313 1314 1315 146 148 147 1323 1...

result:

ok correct!

Subtask #4:

score: 0
Time Limit Exceeded

Dependency #3:

100%
Accepted

Test #60:

score: 4
Accepted
time: 90ms
memory: 48100kb

input:

200000 2
71973 76326
97670 168508
171244 5932
115231 147408
128416 153589
19744 26807
67878 98255
22662 194128
198320 150303
86723 49603
10517 32984
185691 125147
174597 24994
81050 42404
165800 182920
89285 145179
128551 33017
183430 8057
41020 176174
198318 18811
152231 31881
114181 60045
29558 13...

output:

882399295740
1706
1 188460 70658 114345 125662 13738 118312 88056 86342 20469 125150 198830 34184 171733 25207 19094 188755 39714 183607 31328 125185 146149 103823 179243 66259 85349 166905 94524 128306 113506 175419 85783 172850 128380 116967 14671 121935 32772 177196 28309 182363 23520 126355 4470...

result:

ok correct!

Test #61:

score: 0
Accepted
time: 81ms
memory: 46204kb

input:

200000 2
32082 187519
5208 145093
50076 154772
187374 120564
139957 35735
23362 7323
91085 172598
85906 42406
71445 72269
152408 175847
109126 170295
57424 51948
142288 190335
46434 27012
196277 147605
116314 115538
181190 11940
23862 22122
71611 183053
142917 98634
45954 4192
110819 169037
49947 10...

output:

833023647871
1601
1 168670 74461 42679 47846 197507 193300 176275 180727 166695 92511 43467 39799 146165 23625 27565 102454 169208 199030 33416 53139 41207 160947 107708 173852 140499 24046 137147 162828 29429 166803 83672 44352 43797 155400 122620 171907 112784 162293 35944 35384 17828 155360 90578...

result:

ok correct!

Test #62:

score: 0
Accepted
time: 81ms
memory: 48180kb

input:

200000 2
78638 58642
112962 25496
85068 25026
70130 61586
173031 26076
136367 101291
127709 139920
71308 101369
136151 162399
15899 42470
188783 14739
148981 125658
63825 51000
43025 32262
1942 892
186758 34888
111721 75954
15727 114535
43402 80763
159252 40071
178432 174508
140837 145658
110251 183...

output:

859520154059
1660
1 21614 125446 25670 191534 196343 187768 140446 45970 27859 18992 121704 100825 54900 10573 79538 148400 89131 789 144926 27182 178645 5432 190456 44197 136394 68411 65945 190483 142052 99192 156697 37838 170879 66095 56339 174946 37254 46668 22149 43408 135100 124057 179674 12964...

result:

ok correct!

Test #63:

score: 0
Accepted
time: 81ms
memory: 46032kb

input:

200000 2
113130 116994
199787 127733
175019 81432
178540 179218
84082 127210
163623 155486
189624 73275
82498 8202
61848 113067
100558 173153
127108 94716
127580 54314
147631 53398
105967 1535
32421 100984
28479 170565
50049 13612
128342 24121
161245 52286
199917 196293
126521 9391
115032 50698
4507...

output:

942852419968
1789
1 54853 35470 18260 184539 4032 180649 114891 100566 43965 118876 2432 11834 85974 187170 30455 157244 114806 106938 47521 22337 185951 122055 148648 67473 23492 26493 71377 92332 192004 29807 151083 46667 152250 101756 54419 150005 90820 174399 87993 28631 87133 41631 75884 154481...

result:

ok correct!

Test #64:

score: 0
Accepted
time: 84ms
memory: 48236kb

input:

200000 2
77664 54637
84144 154928
72506 50449
160113 77853
194182 38791
107483 80245
9315 30663
148025 33975
102823 42879
52529 135121
22346 28336
97279 42789
117070 88657
79123 108461
132766 124070
106264 167067
191149 170038
150680 124017
122526 80240
22015 134260
180496 175307
74449 114090
104518...

output:

1171517212692
2265
1 102983 154271 97112 170812 10816 9666 71235 136548 1981 158535 115214 34582 17610 30341 74635 139749 32416 54904 164065 21027 131128 47965 141731 26732 110282 162611 194069 8644 27065 94646 62396 12865 8199 61499 191102 31048 160142 149413 52987 199682 80077 31632 31643 165244 5...

result:

ok correct!

Test #65:

score: 0
Accepted
time: 85ms
memory: 46328kb

input:

200000 2
28934 176056
136164 196254
31381 23123
25526 108297
57361 64966
190533 45227
74484 164959
28842 2327
81570 179755
188864 38342
104303 102044
136042 74199
171111 80778
111330 158089
52128 170798
101490 145339
120609 82326
173031 112314
73010 112478
119847 138176
122774 4868
42346 105059
3350...

output:

2326744528710
4529
1 114380 167604 133398 5416 171795 102953 80499 134654 50573 111518 93720 38805 86520 63808 85082 186882 93951 87227 125125 98497 20045 83457 77886 59467 94418 197201 120314 181605 76794 48819 37714 180991 48145 127620 162364 116899 165395 22723 66442 105664 43079 101407 167324 44...

result:

ok correct!

Test #66:

score: 0
Accepted
time: 78ms
memory: 47148kb

input:

200000 2
56021 51529
68684 59222
42913 113684
79211 108152
31389 101993
34308 149833
158947 72984
107009 139522
86949 11829
111788 59214
112750 12966
27645 157963
59289 59222
139737 47437
145601 58355
32220 146798
111541 185862
25607 45580
152343 179102
72458 111092
176999 19531
66379 119683
76547 1...

output:

767459126849
1505
1 123137 81252 27921 69616 78391 183821 29679 177828 114969 9328 22977 163739 83620 4487 62528 196629 188401 10260 49535 7115 99185 40243 160579 147829 158581 129974 17927 75465 164216 199963 187861 158376 117443 89005 130386 110511 190184 26284 130324 81892 102299 3298 24843 12218...

result:

ok correct!

Test #67:

score: 0
Accepted
time: 122ms
memory: 46176kb

input:

200000 2
104390 122869
25883 142866
160515 43820
128440 13022
8318 136414
157868 188440
156836 187687
167016 9347
39806 182142
179923 72411
45877 114238
114548 82833
40280 113331
69170 31456
118069 101689
177443 61482
19872 186357
168183 107559
61588 170900
16642 45648
747 57401
94126 173098
136686 ...

output:

3675388620625
7158
1 156746 25359 182551 171456 6217 58698 76669 46957 81229 104140 107564 43096 196087 49741 18405 71606 17284 46140 169469 68862 3806 60578 21865 49934 98544 124696 96209 186730 73717 120868 172295 148274 37265 117606 53755 167968 145692 11307 151374 3959 82355 73614 35810 173849 1...

result:

ok correct!

Test #68:

score: 0
Accepted
time: 84ms
memory: 49364kb

input:

200000 2
109985 87619
37980 22189
97113 50655
141404 55232
147996 65598
36748 174192
131854 177776
18218 47619
13160 113823
86872 169443
90387 198777
81052 158293
27515 37979
198311 51356
166249 142601
91346 8372
139757 47600
133114 143533
186906 52882
52043 134177
106749 3786
33870 108458
116250 23...

output:

992123589063
1945
1 68194 157597 149879 177461 33891 13650 94283 173999 155315 191943 2177 88983 128930 83935 85868 29637 171497 84624 38048 149357 34401 132730 169319 52698 110927 157097 10613 198350 102904 140302 141943 178279 156933 159047 124714 120543 105056 98157 112560 35504 127323 14687 1736...

result:

ok correct!

Test #69:

score: 0
Accepted
time: 90ms
memory: 46248kb

input:

200000 2
100522 147187
54889 185960
38949 138090
86106 80207
27403 199320
146820 181967
134302 13313
25408 138672
72842 34248
161006 103810
196273 40476
105432 101143
194952 131699
159995 85132
78133 40501
20116 1846
85728 109828
53166 107050
53317 170563
49857 175255
156370 158685
46487 66693
85983...

output:

3540743394022
6910
1 16382 46821 23365 146371 153311 194290 150697 168802 26336 158012 159465 103012 116421 94377 107276 105006 146400 59201 8935 174594 42636 63889 94029 62947 161170 176587 4124 199890 35236 33953 48870 8028 36632 175495 135353 89771 84748 95125 74192 181238 155630 57348 14051 1321...

result:

ok correct!

Test #70:

score: 0
Accepted
time: 75ms
memory: 47352kb

input:

200000 2
89710 128357
3426 66417
52472 91874
31627 100433
198960 160902
176265 76059
70560 72724
139051 191341
512 111102
120209 75664
15138 126122
197008 153163
179022 152817
2515 43991
27182 1020
128784 150584
143001 48543
24479 138105
188695 57568
93380 190780
71186 124797
159152 141009
21133 382...

output:

1337020465724
2654
1 13693 164771 164656 118395 145728 79029 133739 116773 134117 128711 182464 105294 20797 196406 151306 104172 131481 79713 119937 25060 1388 79596 25420 132951 9807 22015 62307 6881 184329 69092 28715 119872 161823 36046 193963 162876 152133 134496 8449 158458 79954 180290 88096 ...

result:

ok correct!

Test #71:

score: 0
Accepted
time: 83ms
memory: 48832kb

input:

200000 2
1 121764
151707 1
1 146498
120892 1
1 167954
37051 1
65946 1
142412 1
1 33774
134506 1
163786 1
1 175250
1 164690
159445 1
1 60645
1 1330
139128 1
121091 1
17510 1
89422 1
20081 1
1 172899
177661 1
1 172826
1 43543
1 177837
28825 1
1 120168
1 38254
1 8601
58920 1
147872 1
1 41335
1 164269
1...

output:

99770036814555
200000
1 121764 146498 120892 167954 37051 65946 142412 33774 134506 163786 175250 164690 159445 60645 1330 139128 121091 17510 89422 20081 172899 177661 172826 43543 177837 28825 120168 38254 8601 58920 147872 41335 164269 142717 2235 77827 38923 6890 164004 189914 51287 51314 76436 ...

result:

ok correct!

Test #72:

score: 0
Accepted
time: 91ms
memory: 48316kb

input:

199999 2
67072 1
92171 150753
90888 151980
49069 30219
174222 9855
195658 1
1 87942
77002 134696
1 65126
109947 3424
145914 162383
1 2757
1 112019
164258 1
66908 62514
185957 1
122946 13227
1 18985
173656 190833
1 102891
1 6832
47914 29907
184372 1
177178 1
174467 87761
132840 1
145220 137302
1 1590...

output:

99914041431818
100002
1 135761 71359 67072 195658 87942 65126 2757 112019 164258 185957 18985 102891 6832 184372 177178 132840 159078 113454 148038 16101 77008 117116 68856 128664 146086 60937 48718 118590 47520 131079 32622 44558 91651 198614 43733 70863 127993 165124 72041 195085 194067 56614 1155...

result:

ok correct!

Test #73:

score: 0
Accepted
time: 98ms
memory: 47512kb

input:

199997 2
181667 73912
70196 155617
57266 177774
146844 22851
17625 44807
140237 145179
71321 26122
119873 142655
42888 1
1 12665
2354 21037
157498 117106
154042 78181
9589 1
46002 137008
19680 124524
133338 79920
1 118916
65513 53811
163778 43702
29017 144717
98739 157944
189251 183682
182803 178046...

output:

49962213918134
50006
1 180804 2544 177685 149002 42888 12665 9589 118916 98573 70815 131340 121671 17422 7097 108910 165181 141826 176793 166101 84566 164449 48670 151440 28546 89451 160627 79042 174818 197212 175855 44478 87893 4722 67241 153469 147268 179610 31528 90140 20389 166773 193752 61741 9...

result:

ok correct!

Test #74:

score: 0
Accepted
time: 78ms
memory: 45776kb

input:

199809 2
169878 4225
23345 92377
98479 42575
149948 72420
50892 90193
47118 16414
69072 47907
48571 63127
149065 40766
143982 72205
169350 85345
154664 137516
154095 72685
95325 102444
101466 119755
32299 39632
58986 95625
177381 137516
36382 110945
69668 129015
97533 177853
32749 35220
121826 30883...

output:

713049791453
1341
1 3214 13776 34605 159467 72184 131684 15137 77456 185879 3525 104905 30931 199335 72722 109248 81509 26119 100984 83258 151934 124114 26223 136053 67005 3646 89167 194608 115529 13056 102189 14182 96328 69690 103747 168053 104871 147207 164612 36463 185614 137314 105796 72634 1487...

result:

ok correct!

Test #75:

score: -4
Time Limit Exceeded

input:

200000 2
5189 138698
162040 22588
64703 112781
3394 136450
174354 3779
21094 6916
88534 109117
134528 32716
199107 74065
151148 26217
128242 194757
185664 167983
19773 60770
11507 105959
161807 139962
38366 176916
185209 97924
54025 141961
190880 55231
43069 120905
94677 20549
79285 158427
82389 310...

output:

200000000000000

result:


Subtask #5:

score: 4
Accepted

Test #83:

score: 4
Accepted
time: 0ms
memory: 26208kb

input:

2000 3
1359 90
1703 163
158 188
360 1501
195 664
1414 215
1546 1756
536 1096
1726 1223
1150 104
1757 703
1982 282
1023 998
1180 419
576 1759
1496 1993
44 670
1703 952
855 849
1998 1399
1280 980
1533 1090
1270 678
1680 387
469 1734
1799 263
473 588
303 226
5 295
1489 1471
1094 1667
1912 210
1368 1360...

output:

1008611451196
2000
1 379 1954 1539 605 1613 1300 1823 1101 1840 562 867 709 88 916 1526 1238 129 1919 816 674 1788 832 297 1903 1349 1808 1428 183 863 951 1522 877 301 775 1265 936 1087 1672 565 1963 1330 926 1325 524 1334 36 46 1019 1231 240 665 1376 289 1427 545 1076 1880 1684 1668 81 1504 1373 19...

result:

ok correct!

Test #84:

score: 0
Accepted
time: 5ms
memory: 26224kb

input:

2000 3
1727 567
1783 1850
205 985
323 1094
1153 821
1756 117
377 1928
1026 1303
1343 1814
268 745
242 948
1140 1218
7 1675
101 1798
1403 1752
1184 671
87 248
1953 30
1580 1441
507 1438
525 419
901 421
1585 1405
1575 883
1952 1930
1988 1325
615 722
994 1202
178 474
1978 1500
899 481
216 409
999 1817
...

output:

1012330476243
2000
1 1789 369 598 525 419 422 269 1079 202 694 88 1918 1589 131 1832 345 1057 1532 1725 761 67 1634 650 1807 719 693 175 234 1935 220 92 1530 1315 257 319 1885 399 750 838 1479 1326 1333 722 615 449 477 1580 517 1441 1561 676 1347 1449 1768 1466 1993 1342 1631 880 84 778 1585 571 190...

result:

ok correct!

Test #85:

score: 0
Accepted
time: 0ms
memory: 26132kb

input:

2000 3
1213 130
101 508
72 1199
1550 1096
1099 861
1515 627
1299 1672
1338 105
1444 1019
15 1560
1949 971
52 1312
30 529
186 1687
1917 484
1971 349
537 1223
1955 1377
300 1060
1786 1811
1960 90
1959 1353
1831 1548
303 511
1073 1197
863 1527
1379 994
31 9
1247 1707
1395 1532
29 1544
119 296
1919 1554...

output:

1001405462082
2000
1 1487 810 1721 1365 1976 605 1986 1255 830 1002 513 1369 1940 668 1557 574 1658 1802 751 1774 1836 1491 1292 374 1010 640 33 1085 1261 1450 242 93 1610 381 1809 222 650 435 181 1527 1899 863 1356 1067 384 1503 1483 854 570 78 358 486 1680 674 63 1709 948 1367 1357 1639 1265 625 1...

result:

ok correct!

Test #86:

score: 0
Accepted
time: 0ms
memory: 26160kb

input:

2000 3
532 64
99 960
1271 519
1141 1056
1986 1889
930 817
639 1188
841 771
1334 179
1336 1163
1687 1909
281 1300
1410 207
1018 1471
1645 972
711 1504
623 1739
1905 1959
1423 738
1747 34
1684 204
61 1012
1092 1350
1977 1130
62 473
1623 1021
1157 227
427 832
1900 1792
1910 584
265 330
1874 1186
1797 1...

output:

1002207066842
2000
1 1093 1948 1011 1848 1348 719 1619 1659 864 861 1808 59 838 1772 1667 313 416 488 103 1178 1762 1068 225 804 1901 1074 233 652 1293 228 351 345 992 1839 994 1430 1913 713 778 618 828 1088 389 403 352 1218 78 1519 63 1742 1396 1166 67 1468 1971 591 731 754 1840 1503 443 1972 1605 ...

result:

ok correct!

Test #87:

score: 0
Accepted
time: 2ms
memory: 24124kb

input:

2000 3
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
2...

output:

995663027103
2000
1 4 16 64 256 1024 1025 512 1026 1027 513 257 1028 1029 514 1030 1031 515 128 258 1032 1033 516 1034 1035 517 259 1036 1037 518 1038 1039 519 129 65 260 1040 1041 520 1042 1043 521 261 1044 1045 522 1046 1047 523 130 262 1048 1049 524 1050 1051 525 263 1052 1053 526 1054 1055 527 1...

result:

ok correct!

Test #88:

score: 0
Accepted
time: 1ms
memory: 26140kb

input:

2000 3
1 2
1 3
1 4
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
5 14
5 15
5 16
6 17
6 18
6 19
7 20
7 21
7 22
8 23
8 24
8 25
9 26
9 27
9 28
10 29
10 30
10 31
11 32
11 33
11 34
12 35
12 36
12 37
13 38
13 39
13 40
14 41
14 42
14 43
15 44
15 45
15 46
16 47
16 48
16 49
17 50
17 51
17 52
18 53
18 54
18 55
19 5...

output:

1000109641799
2000
1 5 41 365 1094 1095 1096 366 1097 1098 1099 367 1100 1101 1102 122 368 1103 1104 1105 369 1106 1107 1108 370 1109 1110 1111 123 371 1112 1113 1114 372 1115 1116 1117 373 1118 1119 1120 124 42 374 1121 1122 1123 375 1124 1125 1126 376 1127 1128 1129 125 377 1130 1131 1132 378 1133...

result:

ok correct!

Test #89:

score: 0
Accepted
time: 3ms
memory: 23924kb

input:

2 3
1 2
820567835 309877233

output:

1130445068
2
1 2 

result:

ok correct!

Test #90:

score: 0
Accepted
time: 0ms
memory: 25940kb

input:

50 3
28 1
40 30
17 31
41 25
1 30
38 6
19 9
50 6
37 4
5 44
13 31
21 46
35 14
25 10
36 41
42 32
37 11
27 20
48 45
31 10
42 17
29 40
26 35
43 3
23 24
27 34
42 39
25 5
7 18
35 48
15 31
30 23
20 17
42 12
39 16
7 32
17 3
41 38
31 47
13 8
33 9
22 33
49 48
29 11
31 19
26 31
41 2
40 17
20 21
4 4 10 2 7 6 3 4...

output:

270
50
1 28 40 11 4 37 29 31 8 13 25 36 38 50 6 2 41 44 5 10 15 47 9 22 33 19 35 14 45 49 48 26 42 7 18 32 16 39 12 20 34 27 46 21 3 43 17 23 24 30 

result:

ok correct!

Test #91:

score: 0
Accepted
time: 3ms
memory: 24112kb

input:

2000 3
1651 76
620 463
764 704
1648 768
1235 1183
915 523
1417 75
758 442
1952 271
1018 947
659 320
1976 562
337 965
1184 35
1234 1609
664 1444
580 737
1331 720
1314 973
945 1890
1760 1986
210 567
186 12
1306 1774
224 1073
1885 314
641 1144
1524 446
1148 1576
859 1438
1991 343
89 1665
140 537
183 14...

output:

994118359072
2000
1 974 1998 917 681 1429 55 1829 1216 1051 802 1006 1047 1575 1666 1291 735 1848 1634 1587 403 41 1241 1895 1064 1932 421 748 1220 489 1726 843 1209 305 13 1012 895 1677 1941 318 1927 334 1905 1352 118 1710 303 892 120 853 1798 1324 1321 59 1614 1674 1925 1966 553 412 296 516 662 39...

result:

ok correct!

Test #92:

score: 0
Accepted
time: 4ms
memory: 24244kb

input:

2000 3
574 1963
1305 849
1271 853
1365 1853
12 1402
1010 1462
1353 494
74 1688
1786 1435
405 1012
1229 924
1085 1565
713 1742
796 1929
1844 1725
801 79
1089 1137
1255 1331
1659 754
341 1929
1233 956
615 1455
1798 867
1105 1943
196 790
1357 678
1160 1797
1310 1963
857 792
35 1464
1576 1251
1628 913
1...

output:

1002312168974
2000
1 27 231 1959 307 1795 1885 1256 1317 202 179 1467 1592 1101 1418 843 676 1911 810 1680 1842 468 1357 1669 1218 397 1312 701 1726 1154 1275 465 711 1804 1710 1441 724 12 175 149 1222 376 1277 628 1341 1083 817 1103 249 1457 1402 990 184 14 48 1624 526 222 704 41 639 1877 90 925 33...

result:

ok correct!

Test #93:

score: 0
Accepted
time: 3ms
memory: 24280kb

input:

2000 3
684 1375
1184 445
1723 1722
473 1351
1019 941
1595 1572
718 56
974 696
308 1015
650 1134
338 1313
210 277
1735 1134
1053 283
1112 1862
90 450
1762 1042
1903 1927
1472 337
312 1925
815 1234
1226 206
1371 994
108 1604
1249 674
1509 1501
1232 1669
1519 1474
1368 780
953 749
1201 1422
351 325
101...

output:

1000468940262
2000
1 427 560 1868 184 769 867 1033 54 925 1582 557 1694 1587 1956 1589 187 26 1096 204 1927 1903 145 659 1818 1767 318 1255 1347 1003 1321 1227 1529 543 1433 104 1151 476 947 1465 271 835 3 98 306 411 331 1839 781 1383 517 114 767 1411 1709 999 1624 1325 581 475 136 1220 1431 37 1897...

result:

ok correct!

Test #94:

score: 0
Accepted
time: 5ms
memory: 24064kb

input:

2000 3
1317 1228
1811 1659
491 1756
1622 1016
730 1196
873 59
1567 441
144 1469
1726 647
698 1631
1985 1711
1005 616
1286 964
1408 625
246 1404
125 1488
16 982
1576 1223
750 1845
1831 604
1502 458
1043 1552
1360 921
180 1800
266 1261
1021 1308
1421 625
99 403
891 1500
602 482
1520 610
486 1899
843 1...

output:

977343950277
2000
1 112 1313 1964 1563 1947 951 1258 1456 1638 913 259 168 1205 1733 1430 113 1597 464 889 350 1860 17 684 1621 1849 631 993 877 1225 1702 544 451 1444 985 452 1558 313 258 1163 1923 319 119 1091 521 1914 1904 1825 898 286 1300 61 823 1417 1928 1554 720 1089 390 1512 1048 39 1292 371...

result:

ok correct!

Test #95:

score: 0
Accepted
time: 6ms
memory: 26036kb

input:

2000 3
1188 1181
1574 1619
944 1974
626 789
1798 27
159 547
1759 1110
1304 1360
1172 997
1815 1043
1496 1948
1781 1513
1884 993
652 1079
1983 1436
88 1953
1221 174
383 1741
48 814
1532 1319
1039 1401
1737 1829
996 920
222 1902
590 1270
692 1504
1918 654
928 1602
208 1165
1251 1596
329 856
1068 577
2...

output:

985678197158
2000
1 219 130 1659 83 708 809 699 388 1676 1219 306 859 816 1716 1846 641 31 1806 478 1205 364 1277 486 1766 700 553 1927 748 1706 577 1068 92 1484 1751 1827 1588 496 439 1593 223 1428 116 373 1524 1312 109 1574 661 1482 366 300 1376 416 879 882 876 1553 558 1721 1330 578 522 671 1957 ...

result:

ok correct!

Test #96:

score: 0
Accepted
time: 4ms
memory: 24100kb

input:

2000 3
892 807
1866 64
123 674
1147 1184
1897 1873
385 1877
7 1697
1753 234
191 1453
625 850
91 1195
320 1560
1827 43
426 1801
1338 1775
55 1070
1138 127
627 1985
225 882
232 1144
124 1208
1665 54
819 898
1038 1676
1642 327
1827 1548
559 1243
69 854
1806 195
943 654
1426 905
691 1598
532 1304
235 53...

output:

1023444069399
2000
1 669 1705 1447 1166 1830 4 1025 1356 781 1519 1299 1256 1544 210 171 1949 577 590 510 1431 362 408 1529 991 154 1109 218 241 248 1516 1143 1940 1711 475 654 943 1780 1323 438 1521 941 337 141 301 1011 679 582 379 873 1828 818 318 1090 117 1037 1341 192 424 924 1061 901 1045 1302 ...

result:

ok correct!

Test #97:

score: 0
Accepted
time: 6ms
memory: 26160kb

input:

2000 3
1367 159
1497 1532
1105 440
1955 1658
129 1964
272 956
1165 1745
625 1694
257 726
645 476
623 1098
648 303
665 847
1304 1665
307 926
319 1098
619 1582
1920 1770
874 1257
1443 815
121 578
1280 943
555 1602
1575 583
545 447
1708 1104
911 146
347 1466
1108 1412
1548 567
451 1182
1449 813
634 168...

output:

1010882805670
2000
1 700 1857 977 1394 743 652 1414 293 194 495 1540 1483 955 856 341 1518 1893 915 717 1109 331 579 1986 51 1585 935 869 1240 1343 1835 1063 1061 1756 157 1563 1969 893 474 1204 1110 719 1622 1118 931 1639 649 91 526 467 1692 390 542 1380 305 1579 334 2000 595 66 725 1868 1836 118 1...

result:

ok correct!

Test #98:

score: 0
Accepted
time: 1ms
memory: 26328kb

input:

2000 3
1611 477
1551 698
1677 1706
712 1391
685 1755
1645 749
1510 671
1952 809
1398 368
213 1597
361 1006
651 971
437 409
1563 1815
704 16
42 404
930 26
1857 1089
1832 173
877 850
1876 1304
349 628
515 241
1700 787
1627 1311
1106 1040
1527 1685
591 1374
1350 359
240 359
456 1245
397 637
297 972
83 ...

output:

1014963178537
2000
1 1785 1787 807 1932 1360 1237 1483 1193 1024 1861 104 504 221 1023 152 862 1733 413 375 793 1045 560 78 301 427 77 1564 198 521 1306 1936 946 1772 1361 1902 1731 463 1268 1771 1798 260 1610 706 938 1757 479 1510 671 610 411 1480 192 9 1081 1835 1513 1491 837 1670 395 766 188 339 ...

result:

ok correct!

Test #99:

score: 0
Accepted
time: 1ms
memory: 26300kb

input:

2000 3
1595 236
1251 497
809 946
633 735
282 191
1643 1997
1563 640
366 1468
640 1510
1781 1617
1157 1659
535 1144
990 1887
687 1221
675 931
214 809
196 724
330 427
596 271
221 1994
947 841
520 640
1251 1215
1331 1042
640 149
1617 1887
202 1223
1400 1429
1127 898
106 1015
615 1707
968 1043
490 1299
...

output:

1003217858982
2000
1 609 1144 522 279 546 602 1183 1432 1072 186 554 1156 738 960 1551 171 889 255 424 596 271 928 75 113 1332 1442 638 1509 416 1002 763 1582 1371 614 392 1718 1046 538 48 1073 1384 1234 905 118 291 1389 529 1555 1542 1687 1414 347 841 1068 1488 298 100 1118 467 155 1151 1023 1957 1...

result:

ok correct!

Test #100:

score: 0
Accepted
time: 1ms
memory: 26036kb

input:

2000 3
988 1
204 1
1 1855
1 226
26 1
1 1079
1 1825
572 1
50 1
1 1215
1 1532
1 1118
1 770
108 1
1 1207
1845 1
432 1
1369 1
1 879
1 203
460 1
154 1
135 1
492 1
1 873
1 1625
1212 1
1 107
1321 1
1818 1
1 292
1 1427
49 1
1 1233
1 1712
1579 1
418 1
1 793
1 1090
1 1842
1302 1
1 227
201 1
1 912
654 1
1 69
1...

output:

996901666648
2000
1 988 204 1855 226 26 1079 1825 572 50 1215 1532 1118 770 108 1207 1845 432 1369 879 203 460 154 135 492 873 1625 1212 107 1321 1818 292 1427 49 1233 1712 1579 418 793 1090 1842 1302 227 201 912 654 69 51 746 1953 354 1172 1656 896 1550 125 1729 297 1234 1940 1336 186 1515 14 1823 ...

result:

ok correct!

Test #101:

score: 0
Accepted
time: 4ms
memory: 26144kb

input:

1999 3
1773 1351
1 1076
1754 1646
1267 1
1157 983
1 978
1 1751
1392 1119
379 1
1 5
1 360
613 769
1 1472
1 1447
851 1
1867 1319
175 1
976 1
1760 1519
1 1718
1 1919
1 835
757 1060
1000 1
1331 1412
338 1
1341 11
1563 1415
1713 1127
772 477
1855 1
168 1248
600 1
335 1825
704 928
236 919
1815 1692
729 57...

output:

1997213132735
1999
1 842 1076 1719 1267 1100 978 1798 1751 1375 379 858 5 1110 360 746 1472 1475 1447 1621 851 216 175 1477 976 1602 1718 1018 1919 1282 835 637 1000 1796 338 532 1855 1770 600 1483 1592 1074 1869 49 1517 899 1874 1382 392 878 1935 856 85 1129 492 1309 953 1740 1205 1817 239 370 1009...

result:

ok correct!

Test #102:

score: 0
Accepted
time: 4ms
memory: 26288kb

input:

1997 3
1399 516
1 716
1426 1537
965 594
1856 855
1284 1479
1566 927
1454 1924
890 1748
84 1373
95 1672
185 1374
1 1082
34 1
211 782
1298 176
1310 776
1661 594
1931 428
980 916
693 1664
1598 91
981 1
30 1
536 121
154 1558
668 641
1637 1
777 13
302 673
889 360
1 1282
929 1
1035 204
1168 1923
190 151
8...

output:

1995219549052
1997
1 522 968 40 716 1350 5 27 1082 1600 511 181 34 1055 584 1384 981 1451 565 1332 30 933 1484 1404 1637 680 65 1977 1282 1010 313 529 929 18 887 954 1478 451 1004 429 996 1708 1922 477 1492 1379 107 825 873 1363 385 679 393 668 1789 1711 641 1894 250 1299 1495 1482 1160 1131 10 311 ...

result:

ok correct!

Test #103:

score: 0
Accepted
time: 1ms
memory: 26172kb

input:

1936 3
341 1240
946 1597
1195 959
1733 1240
615 937
184 592
1258 1799
1601 1409
880 1258
91 1718
1417 1139
916 1592
184 911
1852 180
452 1793
803 1343
180 1895
575 1888
171 1778
1176 1912
1173 107
1173 372
1108 1094
1066 1293
1139 1561
771 1835
651 1675
1637 1675
41 1879
1396 771
1772 497
1687 752
1...

output:

959283331124
1936
1 1793 643 677 1114 112 371 65 1320 1869 1000 433 1198 1167 971 1825 522 1149 855 1911 1111 670 977 986 1326 168 1539 1665 1215 1685 1758 1373 962 856 1517 1744 486 1366 879 380 219 1183 722 461 994 452 206 736 1112 352 1355 884 1818 1152 832 10 1210 396 998 674 1786 1137 6 930 862...

result:

ok correct!

Test #104:

score: 0
Accepted
time: 0ms
memory: 26268kb

input:

2000 3
1370 1319
6 1661
982 1460
654 816
1368 70
841 1391
332 1111
107 46
387 1390
928 196
369 1792
742 337
1906 1604
1278 672
154 1991
1518 308
849 846
705 158
1835 1612
780 1779
881 1867
597 1965
1956 409
1099 1242
828 1821
1662 344
760 1126
911 306
948 1909
1296 830
1642 892
516 1614
957 796
1038...

output:

2000000000000
2000
1 1699 152 1065 1008 155 1616 1486 1792 616 1577 945 383 525 444 690 1212 1542 1749 1436 876 1571 654 661 1267 898 1056 729 846 53 507 430 1433 1430 1923 586 937 454 1987 46 1609 1359 1982 1000 712 241 148 775 16 310 866 1150 713 1518 673 831 695 739 59 1856 1621 1579 208 596 1963...

result:

ok correct!

Test #105:

score: 0
Accepted
time: 5ms
memory: 26400kb

input:

2000 3
531 824
1828 527
489 1172
118 1355
370 562
1080 1962
535 1707
1302 1749
1996 347
424 1282
236 30
1937 1327
395 1060
672 1730
850 1700
19 1215
1989 1284
762 1946
646 1551
1478 249
446 1426
906 1103
1765 267
177 785
1231 699
410 415
1905 1059
1518 1948
219 987
825 1030
1812 995
1260 962
149 786...

output:

987613898700
2000
1 1961 1554 139 1308 1492 1112 1465 683 314 1456 554 1660 884 1412 459 117 1141 10 845 793 1644 107 137 201 185 781 106 866 28 40 1553 335 356 1962 1407 12 50 544 1051 1718 1670 1653 1290 1570 496 1929 286 93 1601 497 1688 1902 1067 1843 1854 787 1062 1596 520 1076 1970 1294 862 23...

result:

ok correct!

Subtask #6:

score: 5
Accepted

Dependency #5:

100%
Accepted

Test #106:

score: 5
Accepted
time: 100ms
memory: 46000kb

input:

200000 3
147012 182751
154277 181776
95094 76426
30313 86629
126223 49995
166060 157842
122541 40371
6521 182375
175030 110447
78367 175134
131250 97285
132337 99771
133031 2158
102720 163461
104670 46325
70722 156875
99733 7253
130400 31525
38020 23547
104556 120340
152061 174001
112957 138331
6972...

output:

99966483941576
200000
1 61368 43786 58507 141601 27342 176539 111660 178830 181337 112530 71702 34966 13484 14314 125180 82821 140683 37316 15351 9486 113272 87198 27399 10792 126290 120906 109219 163260 34236 122694 27536 40031 23180 45724 101123 45844 197484 157652 75696 38555 143826 80568 93617 1...

result:

ok correct!

Test #107:

score: 0
Accepted
time: 93ms
memory: 45424kb

input:

200000 3
88318 81002
165280 125130
123213 158997
170916 134482
177516 24669
83023 47275
56744 198831
61378 114675
142731 71814
37961 109617
197131 149557
68375 143769
129315 188798
47241 2192
45374 89479
141586 98813
117482 28948
47723 198356
153753 15033
74174 89660
120110 20697
166201 153612
56703...

output:

100200484512997
200000
1 137049 133121 122564 79926 132880 152822 180885 5442 123751 165926 149053 126422 115469 185238 18933 61519 179334 84740 113559 188187 34904 70628 118993 72988 3638 167092 175573 5614 165640 132793 184160 112962 75313 153829 110350 87835 153946 35054 192100 128743 67578 32252...

result:

ok correct!

Test #108:

score: 0
Accepted
time: 108ms
memory: 45516kb

input:

200000 3
158080 150707
87713 27325
92660 116209
54409 23694
2943 189354
174240 164818
63040 89575
78660 136513
161745 60054
17228 137313
33135 77303
46614 163540
176388 144256
20069 160599
164840 98121
163973 193193
93832 65863
151238 29299
13510 176374
95565 29436
172499 151626
4052 2523
149429 151...

output:

99876819168945
200000
1 123803 1012 78719 191267 57281 4535 198494 49778 36748 46197 75819 176040 132601 167651 112505 122093 64819 149225 98228 106394 103825 89318 186423 179479 153121 175233 165448 34517 178947 123835 30991 962 130952 190733 165889 194629 190142 179548 183005 43914 107871 13737 12...

result:

ok correct!

Test #109:

score: 0
Accepted
time: 118ms
memory: 45496kb

input:

200000 3
13458 31389
54935 62559
19438 94761
190500 137721
133057 27282
118646 10976
158688 189150
50966 88936
64367 138380
1248 98893
70840 18433
7913 117595
102418 46367
54395 8227
170625 128662
95469 29899
156391 75448
147167 88351
146838 184391
77624 107403
24058 128408
178325 168636
48464 73268...

output:

99910494745784
200000
1 182149 15678 110982 191608 138065 161591 169389 174566 75938 53081 64228 56334 105987 56453 31491 93436 109029 172128 62429 178222 22289 85191 171140 20735 59766 185203 115099 48929 176355 157237 3160 89222 157476 153718 197605 148884 76366 5076 156327 59081 56522 187648 1704...

result:

ok correct!

Test #110:

score: 0
Accepted
time: 103ms
memory: 46320kb

input:

200000 3
57046 131800
29987 88605
171474 148623
99129 28902
45321 30680
75505 16586
12530 86028
120454 7164
33933 150164
82906 37260
121117 104053
192033 47278
37159 45570
153727 27709
16556 116173
105577 75450
55530 147064
27341 46913
36453 101815
29637 43794
123623 61867
3629 59534
75839 5762
3583...

output:

100006037268766
200000
1 153415 182427 38806 95837 99599 183498 143132 165677 146327 23561 196486 60410 17274 84320 184179 92625 36052 147240 158882 37817 169829 111591 102926 97695 63070 164757 154592 118047 42603 165624 110328 61247 169744 122836 121274 77839 67344 26883 195663 96494 109219 49341 ...

result:

ok correct!

Test #111:

score: 0
Accepted
time: 116ms
memory: 46860kb

input:

200000 3
139477 43272
191114 76077
179020 189948
28137 1021
65951 108562
103570 145873
115851 178975
178592 72360
173350 154567
84335 161076
142716 153606
185307 176576
104994 143521
73511 116320
168667 92228
160372 179510
78166 57346
137423 155483
76454 179369
194690 69013
2700 101118
100200 94223
...

output:

99890707584446
200000
1 71778 179451 25269 59226 120008 20458 30188 11895 57067 170549 54107 54517 154676 161247 68419 59363 154633 17703 76027 6879 64910 62649 175049 23086 151883 4017 151253 12541 173685 78185 29393 6488 78733 121575 139523 144197 79811 169360 70380 116864 103928 112251 45454 1996...

result:

ok correct!

Test #112:

score: 0
Accepted
time: 79ms
memory: 47756kb

input:

200000 3
179253 61326
193064 25770
101250 104257
127308 168366
75652 156351
48789 45946
3246 138024
161405 143701
41976 91073
162591 27995
104694 9725
96951 60586
170891 35876
127049 121655
51111 162908
75978 187533
87785 85717
12359 132567
161307 112872
153158 48573
98012 48629
103902 196093
99788 ...

output:

99804652763041
200000
1 157756 162801 158751 135568 172921 1591 105368 166157 161125 123631 25430 61669 143259 85541 149651 9707 44782 77934 70938 53577 132294 7433 159486 7192 65812 194950 123700 198332 19361 193650 174620 156239 120843 137493 140172 85930 92791 179647 15550 141269 65527 142282 224...

result:

ok correct!

Test #113:

score: 0
Accepted
time: 121ms
memory: 45140kb

input:

200000 3
62838 75939
87826 180015
72625 160066
31793 97154
87330 68381
163447 73473
12778 146477
175129 158989
171461 14472
86022 120141
194508 29080
158722 75883
50290 83476
106106 21819
178861 182937
166058 96930
179108 125006
199570 132827
170051 193208
121118 189720
86617 54823
184821 60430
8819...

output:

100006003713207
200000
1 108035 3447 188640 3132 68471 39710 48343 42342 46025 176553 187063 49806 13336 19633 144122 74490 23805 30283 69160 26201 189901 351 99889 840 76196 64002 69980 131982 7102 52461 116230 147086 41042 104 182351 170363 23164 131892 159474 68371 39369 176423 77525 64463 31234 ...

result:

ok correct!

Test #114:

score: 0
Accepted
time: 72ms
memory: 46388kb

input:

200000 3
153989 10517
27314 72036
93500 132724
93638 100042
192943 181118
59968 98240
154528 61181
20366 181919
7218 87940
38589 133947
154187 77410
116666 2957
70560 16300
128562 51840
109869 105397
60196 3012
161863 18667
36797 61682
180020 54807
127767 42942
90184 125480
96410 114460
178356 14309...

output:

100132596896132
200000
1 7430 159319 159716 184842 79687 50215 76962 142609 100597 47453 18647 194348 170251 56711 106890 34147 21220 165670 185504 154158 119720 32039 192097 56501 162236 69862 172751 116616 104123 82910 116155 15167 41432 29664 195434 86612 137609 116658 74369 147470 31975 654 1069...

result:

ok correct!

Test #115:

score: 0
Accepted
time: 93ms
memory: 45672kb

input:

200000 3
193823 30011
91709 11809
501 45254
82025 86617
184348 23880
103950 119507
37454 8974
174384 115451
23634 107320
97650 182412
42066 177636
111315 60332
130053 54528
1558 155819
7733 158979
164488 110559
46281 59042
72138 22510
13718 2327
133303 92964
105935 168350
39293 164483
15208 86000
84...

output:

99823050174586
200000
1 126235 76871 140207 45547 54528 44975 117111 134669 83526 130053 64714 33183 26273 80841 85098 141431 146341 161892 198789 30077 99570 59600 177827 35660 189819 197663 123609 55814 64424 36177 22761 100789 34775 28417 55113 130212 175669 45995 121694 154722 32897 196620 56636...

result:

ok correct!

Test #116:

score: 0
Accepted
time: 85ms
memory: 48120kb

input:

200000 3
167904 154479
99791 26520
66032 21354
89797 127514
81807 174766
2597 165492
80439 48156
101761 132200
96442 63449
199372 164659
160562 84653
92296 7081
71393 42324
196440 127414
61112 184736
80407 46397
193310 58007
189525 22158
112277 132008
187852 91575
33497 40060
121384 1910
174332 7252...

output:

100032502601811
200000
1 71912 15635 52491 130139 157470 129176 126467 116375 38460 156962 55827 191493 118737 6313 45963 51862 54720 195138 144913 150329 175456 176897 149266 94206 528 40203 139095 96987 181315 130599 19714 197907 113414 127849 133548 125077 31031 68281 160809 171459 11290 40520 64...

result:

ok correct!

Test #117:

score: 0
Accepted
time: 64ms
memory: 44772kb

input:

200000 3
57696 1
1 118308
1 63302
143342 1
1 32977
169723 1
1 99113
1 20536
104991 1
1 176676
1 35771
1 199270
1 140871
1 71858
77751 1
133782 1
1 116525
63323 1
1 82450
125231 1
1 57698
1 192616
1 127854
168916 1
25125 1
73904 1
38396 1
1 4002
192295 1
150580 1
1 159320
1 62139
46661 1
1 150820
1 4...

output:

100188092398438
200000
1 57696 118308 63302 143342 32977 169723 99113 20536 104991 176676 35771 199270 140871 71858 77751 133782 116525 63323 82450 125231 57698 192616 127854 168916 25125 73904 38396 4002 192295 150580 159320 62139 46661 150820 44895 161850 81349 77478 196641 142082 54519 85648 1246...

result:

ok correct!

Test #118:

score: 0
Accepted
time: 69ms
memory: 43216kb

input:

199999 3
85151 130580
91456 1
1 126463
75828 52651
1 166438
97319 1
142822 72349
86125 191843
42036 15244
79975 99266
1 43347
1 136116
144573 104329
70554 1
154747 1
36845 1805
44410 1
182186 83316
155755 1
71223 129018
1 127862
1 78098
195817 18601
1 194275
1 85673
12603 92383
14771 191475
112155 1...

output:

199823206822200
199999
1 44657 91456 108452 126463 118937 166438 94576 97319 132319 43347 127963 136116 183123 70554 5003 154747 181730 44410 172396 155755 162404 127862 112742 78098 119131 194275 139728 85673 75012 112155 42969 121815 151737 179498 135199 75557 100511 100382 2682 86774 100921 18704...

result:

ok correct!

Test #119:

score: 0
Accepted
time: 89ms
memory: 45092kb

input:

199997 3
131613 140540
69978 138510
168678 157222
178811 3528
18491 28791
101558 152962
181277 930
134819 58137
2395 48734
147095 1
186977 95913
8298 1
179118 19885
27772 137115
62062 22064
27659 63226
91886 588
2211 1
1 2193
27574 1
96584 59043
46821 111679
6754 156644
140820 130625
114787 1
57183 ...

output:

199821436893275
199997
1 40782 176347 142331 147095 56817 146032 180790 8298 80154 180695 73637 2211 111989 94187 156535 2193 195744 186581 6555 27574 130951 101135 199314 114787 176865 64820 42143 17971 28292 82328 131214 197493 15050 60959 90998 1784 135194 167448 193506 159388 174311 195359 13931...

result:

ok correct!

Test #120:

score: 0
Accepted
time: 98ms
memory: 45436kb

input:

199809 3
94685 130894
41571 74291
26864 192447
123025 103411
12655 63756
121771 108019
65438 48656
176986 96765
10202 194287
108921 26742
51953 110771
87549 119680
133398 172870
85286 49434
144205 158162
157948 108072
59452 52518
103411 185204
170486 73773
140828 61920
160006 153902
186600 142638
33...

output:

100198293228920
199809
1 39501 1535 89809 61038 131591 84703 3727 125941 20201 150372 132357 65559 37827 69367 92864 162664 86958 71616 116492 14866 8890 12284 42665 172420 93976 53591 11690 52188 86643 138337 60519 118388 180651 98722 167735 117061 141151 143010 14670 53590 79352 136487 132199 3849...

result:

ok correct!

Test #121:

score: 0
Accepted
time: 134ms
memory: 57924kb

input:

200000 3
9586 193144
171563 40905
6622 65112
70106 27821
188019 98031
47484 179201
43370 65160
62820 27032
152546 143501
125446 69794
135672 118195
27893 16069
172623 134805
164806 148766
108617 14368
66935 108798
159549 983
14719 163836
173818 163624
24054 100996
151308 144701
130442 142208
142769 ...

output:

200000000000000
200000
1 4538 121952 179585 86793 149077 188525 103155 143762 89783 97753 192471 184882 142397 168109 178895 57407 103744 128769 118927 136732 64237 63338 47463 95403 1323 174747 122411 103074 127920 369 3539 115111 4291 116221 146572 91034 109240 106855 61817 85620 91238 146022 1632...

result:

ok correct!

Test #122:

score: 0
Accepted
time: 131ms
memory: 52812kb

input:

200000 3
5381 142906
195916 107149
28028 86513
140805 179412
120296 155640
88810 138241
67680 36075
18302 103548
197422 113736
107225 185275
96224 191998
71426 84989
148160 128735
7180 115757
72027 78126
132940 2260
68261 167840
11075 11586
136344 159122
71717 66896
3688 131894
188506 19576
177339 4...

output:

99938006915289
200000
1 138973 34556 135207 69269 148746 53259 27491 196612 649 44775 90763 167691 103466 184158 142472 42907 137009 173910 127703 73659 112133 48472 66353 168822 90077 86388 4314 80321 25845 75424 30013 157334 91048 155556 165487 108868 195837 183880 158134 5101 153193 73021 151047 ...

result:

ok correct!

Test #123:

score: 0
Accepted
time: 107ms
memory: 51292kb

input:

200000 3
81359 23709
47617 60906
88252 102848
98019 112549
30197 80744
65659 97659
158878 19909
94219 11691
86418 94004
59681 135769
143977 151753
77274 138576
30461 150335
85619 146257
168877 47780
141821 36612
36628 12386
3027 198618
98013 74369
156285 199585
5968 75053
144088 37775
44797 3792
133...

output:

100070095386096
200000
1 141962 118600 82149 161437 18430 164092 137537 93202 189414 175092 53129 4313 7312 122304 139855 24754 156966 86939 68610 152692 54103 16166 59957 34633 135195 9051 187102 9085 96183 20655 9425 166337 59809 80279 117432 65706 88058 199198 115739 32237 14722 118563 170165 399...

result:

ok correct!

Test #124:

score: 0
Accepted
time: 129ms
memory: 50008kb

input:

200000 3
44823 19469
157522 45675
35223 33063
48384 43574
153370 51203
50021 198093
2217 130181
148628 37413
65646 9542
12916 145699
99195 110491
55343 51767
71138 8376
188306 160428
198328 139379
70854 18315
48129 43378
142336 95958
25165 189153
174301 27234
184222 93794
179422 38902
76681 78714
11...

output:

100106249361173
200000
1 72519 192477 20072 68073 63583 100340 121975 173750 766 107543 194409 8234 17970 198631 23825 108913 93696 143622 49556 113369 58344 29523 199323 194653 182144 92516 170504 158015 133830 113097 154619 132830 199557 168819 147607 199751 58337 143991 158221 58803 104283 19331 ...

result:

ok correct!

Test #125:

score: 0
Accepted
time: 108ms
memory: 49424kb

input:

200000 3
66925 159827
183145 173667
142615 151805
40331 125850
86779 21981
193285 55703
16332 64097
128674 29528
54281 177585
19905 93782
8189 66728
71597 107045
32330 126864
156780 162970
13291 153811
79967 4617
56093 197260
58256 844
51390 86594
192713 154318
161746 34026
127522 198605
36672 18301...

output:

100002327466724
200000
1 188596 149924 188758 198221 48421 28287 50164 110268 182419 16264 173228 178228 93563 10102 67468 162200 174046 192168 37632 7723 186710 101235 185990 152665 87246 54474 172974 98815 81851 92007 121053 109339 28603 196958 151036 131212 126678 69047 84969 135933 13512 108716 ...

result:

ok correct!

Test #126:

score: 0
Accepted
time: 80ms
memory: 47920kb

input:

200000 3
50618 142550
5660 103232
108320 43974
83591 71194
150884 191741
143985 51298
153093 87002
46612 90512
140403 27213
68268 191693
192026 183039
4113 198531
149099 49121
21431 59973
76644 153024
66828 94440
178145 174081
162793 31269
101449 54928
110314 93043
58967 49470
136375 71440
174999 11...

output:

99965628723367
200000
1 83983 97802 108491 103766 113307 82909 92524 193488 119940 18411 154223 187395 173916 128219 19287 145743 183833 154883 103283 152389 171683 21068 196674 137771 29846 35649 7856 52556 199514 180012 120003 190280 50514 109904 18798 145397 81993 28960 5739 77451 7390 7839 11676...

result:

ok correct!

Test #127:

score: 0
Accepted
time: 45ms
memory: 47764kb

input:

200000 3
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54...

output:

99887916695349
200000
1 4 16 64 256 1024 4096 16384 65536 131072 131073 65537 131074 131075 32768 65538 131076 131077 65539 131078 131079 32769 16385 65540 131080 131081 65541 131082 131083 32770 65542 131084 131085 65543 131086 131087 32771 8192 16386 65544 131088 131089 65545 131090 131091 32772 6...

result:

ok correct!

Test #128:

score: 0
Accepted
time: 43ms
memory: 45760kb

input:

200000 3
1 2
1 3
1 4
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
5 14
5 15
5 16
6 17
6 18
6 19
7 20
7 21
7 22
8 23
8 24
8 25
9 26
9 27
9 28
10 29
10 30
10 31
11 32
11 33
11 34
12 35
12 36
12 37
13 38
13 39
13 40
14 41
14 42
14 43
15 44
15 45
15 46
16 47
16 48
16 49
17 50
17 51
17 52
18 53
18 54
18 55
19...

output:

100298991530485
200000
1 5 41 365 3281 29525 88574 88575 88576 29526 88577 88578 88579 29527 88580 88581 88582 9842 29528 88583 88584 88585 29529 88586 88587 88588 29530 88589 88590 88591 9843 29531 88592 88593 88594 29532 88595 88596 88597 29533 88598 88599 88600 9844 3282 29534 88601 88602 88603 2...

result:

ok correct!