QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#35676#4270. Double Attendancep_b_p_b25 ✓770ms269824kbC++175.7kb2022-06-17 22:05:292022-06-17 22:05:30

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-17 22:05:30]
  • 评测
  • 测评结果:25
  • 用时:770ms
  • 内存:269824kb
  • [2022-06-17 22:05:29]
  • 提交

answer

#include<bits/stdc++.h>
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define pll pair<ll,ll>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	#define sz 333333
	typedef long long ll;
	typedef double db;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
	char __sr[1<<21],__z[20];int __C=-1,__zz=0;
	inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
	inline void print(int x)
	{
		if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
		while(__z[++__zz]=x%10+48,x/=10);
		while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
	}
	void file()
	{
		#ifdef NTFOrz
		freopen("a.in","r",stdin);
		#endif
	}
	inline void chktime()
	{
		#ifdef NTFOrz
		cerr<<clock()/1000.0<<'\n';
		#endif
	}
	#ifdef mod
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
	ll inv(ll x){return ksm(x,mod-2);}
	#else
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
	#endif
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

int n,m; ll K;
struct hh{ll l,r;bool operator < (const hh &a) const {return l<a.l;}}a[sz],b[sz];
int opA[sz],opB[sz];
int idA[sz][2],idB[sz][2],cc;
vector<pii>V[sz<<2];
int dp[sz<<2];

// x ÊôÓÚÄĸöÏ߶Σ»Èç¹ûÄĸö¶¼²»ÊôÓÚ¾ÍÍùÇ°×ß 
int findA(ll x){int p=upper_bound(a+1,a+n+1,(hh){x,x})-a-1;if (p!=0&&a[p].r>=x) return p;return p+1;}
int findB(ll x){int p=upper_bound(b+1,b+m+1,(hh){x,x})-b-1;if (p!=0&&b[p].r>=x) return p;return p+1;}

int __CUR;
pll _tr[2][sz<<2];
#define tr _tr[__CUR]
#define ls k<<1
#define rs k<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
void build(int k,int l,int r,hh *a)
{
	if (l==r) return tr[k]=MP(a[l].l-2ll*K*l,a[l].r-2ll*K*l),void();
	int mid=(l+r)>>1;
	build(lson,a),build(rson,a);
	tr[k]=MP(max(tr[ls].fir,tr[rs].fir),min(tr[ls].sec,tr[rs].sec));
}
int query(int k,int l,int r,int st,ll x)
{
	if (r<st) return -1;
	if (x>=tr[k].fir&&x<=tr[k].sec) return -1;
	if (l==r) return l;
	int mid=(l+r)>>1;
	int res=query(lson,st,x);
	if (res!=-1) return res;
	return query(rson,st,x);
}

void work()
{
	__CUR=0; build(1,1,n+1,a);
	__CUR=1; build(1,1,m+1,b);
	auto GO=[](int i,int j,int l,int r,int del,int c,ll x)
	{
		rep(_,1,4)
		{
			x+=K;
			if (b[r].l>x||b[r].r<x)
			{
				r=findB(x);
				if (b[r].l<x) c+=(r!=del),++r;
				V[idA[i][j]].push_back(MP(idB[r][opB[r]==l],c+1));
				return 0;
			}
			V[idA[i][j]].push_back(MP(idB[r+1][opB[r+1]==l],c+(r!=del)+1));
			c+=(r!=del); del=l;
			++l;
			x+=K;
			if (a[l].l>x||a[l].r<x)
			{
				l=findA(x);
				if (a[l].l<x) c+=(l!=del),++l;
				V[idA[i][j]].push_back(MP(idA[l][opA[l]==r],c+1));
				return 0;
			}
			V[idA[i][j]].push_back(MP(idA[l+1][opA[l+1]==r],c+(l!=del)+1));
			c+=(l!=del); del=r;
			++r;
		}
		return 1;
	};
	chktime();
	rep(i,1,n)
	{
		ll x=a[i].l;
		int t=findB(x+K);
		int _;
		rep(j,0,1)
		{
			int l=i,r=t,del=(j?opA[i]:0),c=0;
			_=GO(i,j,l,r,del,c,x);
		}
		if (!_) continue;
		__CUR=0; int af=query(1,1,n+1,i+1,x+2ll*K-2ll*(i+1)*K);
		__CUR=1; int bf=query(1,1,m+1,t,x+K-2ll*t*K);
		rep(j,0,1)
		{
			int l=i,r=t,del=(j?opA[i]:0),c=(del!=t);
			int k=max(1,min(af-i-1,bf-t-1)-1); l+=k,r+=k,c+=2*k-1,x+=2*k*K; del=r-1;
			GO(i,j,l,r,del,c,x);
		}
	}
}

void DP()
{
	static pii id[sz<<2]; int cc=0;
	rep(i,1,n+1) rep(j,0,1) id[++cc]=MP(a[i].l,idA[i][j]);
	rep(i,1,m+1) rep(j,0,1) id[++cc]=MP(b[i].l,idB[i][j]);
	sort(id+1,id+cc+1);
	static int pre[sz]; rep(i,1,cc) pre[id[i].sec]=i;
	memset(dp,~0x3f,sizeof(dp));
	dp[idA[1][0]]=1;
	rep(i,1,cc) for (auto p:V[id[i].sec]) chkmax(dp[p.fir],dp[id[i].sec]+p.sec);
}

int main()
{
	file();
	read(n,m,K);
	rep(i,1,n) read(a[i].l,a[i].r),--a[i].r;
	rep(i,1,m) read(b[i].l,b[i].r),--b[i].r;
	sort(a+1,a+n+1),sort(b+1,b+m+1);
	int added=0;
	if (a[1].l!=0) { added=1; ++n; drep(i,n,2) a[i]=a[i-1]; a[1]=hh{0,0}; }
	a[n+1]=b[m+1]=hh{int(2e9)+1,int(2e9)+1};
	rep(i,1,n+1) opA[i]=findB(a[i].l),opA[i]=((opA[i]!=-1&&b[opA[i]].l<=a[i].l)?opA[i]:m+i+1);
	rep(i,1,m+1) opB[i]=findA(b[i].l),opB[i]=((opB[i]!=-1&&a[opB[i]].l<=b[i].l)?opB[i]:n+i+1);
	rep(i,1,n+1) rep(j,0,1) idA[i][j]=++cc; rep(i,1,m+1) rep(j,0,1) idB[i][j]=++cc;
	chktime();
	
	// ÎÞÄÔÍùÇ°×ß 
	rep(i,1,n) rep(j,0,1) V[idA[i][j]].push_back(MP(idA[i+1][j&&opA[i]==opA[i+1]],1));
	rep(i,1,m) rep(j,0,1) V[idB[i][j]].push_back(MP(idB[i+1][j&&opB[i]==opB[i+1]],1));
	chktime();
	
	// Ïò¶ÔÃæÌø
	work();
	{
		int _=sz-1;
		rep(i,0,_) swap(a[i],b[i]),swap(opA[i],opB[i]);
		rep(i,0,_) rep(j,0,1) swap(idA[i][j],idB[i][j]);
		swap(n,m);
	}
	chktime();
	work();
	{
		int _=sz-1;
		rep(i,0,_) swap(a[i],b[i]),swap(opA[i],opB[i]);
		rep(i,0,_) rep(j,0,1) swap(idA[i][j],idB[i][j]);
		swap(n,m);
	}
	chktime();
	
	DP();
	chktime();
	cout<<dp[idA[n+1][0]]-1-added;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 17ms
memory: 60400kb

input:

3 1 8
10 20
100 101
20 21
15 25

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 21ms
memory: 60392kb

input:

1 5 3
1 100
1 2
2 3
3 4
4 5
5 6

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 12ms
memory: 60324kb

input:

10 10 5
4 9
43 48
69 70
70 72
52 67
75 83
100 103
103 1501
10 27
28 40
5 7
27 29
30 39
40 42
42 45
67 80
0 5
45 59
10 20
22 23

output:

18

result:

ok single line: '18'

Test #4:

score: 0
Accepted
time: 17ms
memory: 60336kb

input:

1 1 1
0 1
0 1

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 15ms
memory: 60424kb

input:

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

output:

10

result:

ok single line: '10'

Test #6:

score: 0
Accepted
time: 10ms
memory: 60464kb

input:

10 10 90
1440 1620
0 180
1080 1260
900 1080
180 360
720 900
540 720
360 540
1620 1800
1260 1440
1170 1350
990 1170
1530 1710
1350 1530
90 270
450 630
270 450
630 810
810 990
1710 1890

output:

20

result:

ok single line: '20'

Test #7:

score: 0
Accepted
time: 16ms
memory: 60324kb

input:

10 10 90
1080 1260
1440 1620
900 1080
1620 1800
180 360
360 540
540 720
1800 1980
1260 1440
720 900
90 270
1710 1890
810 990
1170 1350
1530 1710
630 810
1350 1530
990 1170
450 630
270 450

output:

20

result:

ok single line: '20'

Test #8:

score: 0
Accepted
time: 20ms
memory: 60296kb

input:

10 10 166
1 2
664 996
332 664
1660 1992
0 1
1328 1660
996 1328
3 4
2 3
4 5
333 334
1494 1826
498 830
1162 1494
334 335
336 337
0 332
830 1162
335 336
332 333

output:

20

result:

ok single line: '20'

Test #9:

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

input:

10 10 166
2 3
0 1
3 4
1328 1660
1999 2000
996 1328
1 2
332 664
4 5
664 996
334 335
335 336
333 334
1162 1494
0 332
498 830
336 337
830 1162
332 333
1999 2000

output:

19

result:

ok single line: '19'

Test #10:

score: 0
Accepted
time: 22ms
memory: 60196kb

input:

10 10 1
1607 1721
327 413
222 264
1744 1746
35 50
619 766
995 1127
1421 1541
1236 1294
984 995
626 1122
1313 1386
65 141
1394 1428
1553 1764
1766 1990
1551 1552
465 531
1500 1531
623 625

output:

20

result:

ok single line: '20'

Test #11:

score: 0
Accepted
time: 23ms
memory: 60324kb

input:

10 10 1000000000
664 1247
157 183
1975 1986
1289 1374
1448 1461
233 326
1888 1913
183 194
1927 1933
1499 1672
1138 1387
402 652
266 396
1439 1452
1954 1956
684 737
1700 1887
1576 1678
1473 1485
886 1004

output:

10

result:

ok single line: '10'

Test #12:

score: 0
Accepted
time: 24ms
memory: 60320kb

input:

10 10 3
786 792
1395 1579
1348 1371
303 371
430 431
1331 1343
813 1050
1833 1853
654 706
622 634
237 302
1261 1266
49 216
1514 1524
1524 1607
1004 1018
748 918
1020 1141
1967 1994
1710 1735

output:

20

result:

ok single line: '20'

Test #13:

score: 0
Accepted
time: 20ms
memory: 60432kb

input:

10 10 4
82 206
370 769
1086 1131
267 330
836 984
995 1052
778 805
1880 1956
1956 1999
1531 1761
1687 1730
1879 1968
694 710
441 674
738 1302
1734 1737
1357 1365
1372 1604
1606 1672
722 726

output:

20

result:

ok single line: '20'

Test #14:

score: 0
Accepted
time: 8ms
memory: 60320kb

input:

10 10 9
1667 1724
266 375
1736 1936
1312 1659
858 886
442 708
193 198
1127 1244
383 428
935 1021
614 628
1797 1832
199 218
229 268
386 404
413 587
962 1248
814 878
1462 1732
1420 1424

output:

20

result:

ok single line: '20'

Test #15:

score: 0
Accepted
time: 16ms
memory: 60324kb

input:

10 10 16
14 88
1638 1644
645 970
1218 1232
1401 1589
1972 1994
1657 1721
1145 1188
1243 1246
179 244
1925 1958
355 433
706 832
564 587
12 270
1541 1728
1499 1529
294 348
1160 1205
1004 1032

output:

20

result:

ok single line: '20'

Test #16:

score: 0
Accepted
time: 29ms
memory: 60192kb

input:

10 10 64
998 1233
1868 1888
1898 1943
1811 1818
243 292
185 202
205 211
342 454
1269 1313
970 973
770 1192
1424 1435
710 715
60 74
77 250
1992 1998
715 758
1393 1397
1523 1695
359 439

output:

20

result:

ok single line: '20'

Test #17:

score: 0
Accepted
time: 17ms
memory: 60332kb

input:

10 10 31
1755 1831
1513 1514
559 565
1557 1727
1891 1997
56 159
527 544
1745 1749
572 1106
483 504
1789 1824
1306 1439
1680 1789
1490 1528
1089 1144
832 1010
18 306
813 820
598 757
1184 1229

output:

19

result:

ok single line: '19'

Test #18:

score: 0
Accepted
time: 16ms
memory: 60320kb

input:

10 10 995
1139 1304
1108 1135
1682 1771
1897 1913
244 404
1359 1362
1385 1608
420 496
787 1053
562 769
506 514
164 315
324 338
699 1240
1936 1957
634 695
385 454
20 107
525 621
1920 1931

output:

10

result:

ok single line: '10'

Test #19:

score: 0
Accepted
time: 8ms
memory: 60404kb

input:

10 10 1256
1757 1979
898 939
486 649
1074 1085
1346 1584
1201 1345
1013 1034
1070 1071
1109 1198
56 398
587 588
589 615
49 65
338 467
1201 1252
559 578
635 689
706 743
1495 1831
995 1043

output:

10

result:

ok single line: '10'

Test #20:

score: 0
Accepted
time: 13ms
memory: 60460kb

input:

10 10 1554
951 962
1902 1934
1220 1367
1499 1621
386 387
993 1127
536 813
1862 1893
526 532
401 431
1048 1050
986 990
609 645
793 957
1945 1989
521 548
1057 1063
1137 1823
1004 1017
229 459

output:

10

result:

ok single line: '10'

Test #21:

score: 0
Accepted
time: 21ms
memory: 60324kb

input:

10 10 324854
1281 1570
126 135
1900 1963
1578 1583
1593 1693
17 98
1079 1246
1832 1850
187 449
569 739
1960 1970
1262 1402
1704 1707
940 1104
1628 1676
1716 1727
1808 1869
1877 1892
1560 1565
145 337

output:

10

result:

ok single line: '10'

Test #22:

score: 0
Accepted
time: 20ms
memory: 60404kb

input:

10 10 73118142
223 258
514 576
1173 1204
712 1162
653 656
342 458
1633 1831
1891 1923
1288 1609
133 206
118 138
1440 1494
1332 1432
152 509
65 109
712 748
1532 1578
611 669
1946 1957
513 519

output:

10

result:

ok single line: '10'

Test #23:

score: 0
Accepted
time: 11ms
memory: 60316kb

input:

1 1 217
366 1554
481 937

output:

2

result:

ok single line: '2'

Test #24:

score: 0
Accepted
time: 11ms
memory: 60396kb

input:

1 1 223
1577 1888
243 879

output:

2

result:

ok single line: '2'

Test #25:

score: 0
Accepted
time: 16ms
memory: 60416kb

input:

1 1 95
1009 1709
1182 1759

output:

2

result:

ok single line: '2'

Test #26:

score: 0
Accepted
time: 15ms
memory: 60324kb

input:

1 1 39
1210 1758
864 1497

output:

2

result:

ok single line: '2'

Test #27:

score: 0
Accepted
time: 8ms
memory: 60312kb

input:

1 1 197
426 1381
926 1911

output:

2

result:

ok single line: '2'

Test #28:

score: 0
Accepted
time: 17ms
memory: 60192kb

input:

2 2 259
1047 1333
1560 1784
1587 1963
31 532

output:

4

result:

ok single line: '4'

Test #29:

score: 0
Accepted
time: 9ms
memory: 60316kb

input:

2 2 263
942 1287
1472 1620
610 783
1123 1183

output:

3

result:

ok single line: '3'

Test #30:

score: 0
Accepted
time: 15ms
memory: 60252kb

input:

2 2 12
709 1247
1344 1924
1973 1993
256 811

output:

4

result:

ok single line: '4'

Test #31:

score: 0
Accepted
time: 21ms
memory: 60288kb

input:

2 2 289
1936 1962
111 426
699 717
757 1534

output:

4

result:

ok single line: '4'

Test #32:

score: 0
Accepted
time: 13ms
memory: 60320kb

input:

10 2 13
728 734
1682 1716
1962 1964
917 918
1028 1220
455 459
1514 1537
505 588
1968 1986
1336 1441
1838 1842
904 1063

output:

12

result:

ok single line: '12'

Test #33:

score: 0
Accepted
time: 28ms
memory: 60420kb

input:

10 2 147
1684 1853
1562 1611
1217 1246
519 586
1104 1130
121 267
1461 1528
1555 1558
467 512
457 467
1764 1803
891 1103

output:

11

result:

ok single line: '11'

Test #34:

score: 0
Accepted
time: 19ms
memory: 60392kb

input:

2 10 105
1429 1992
1994 2000
312 356
1285 1307
247 283
822 827
1327 1908
205 214
456 697
784 803
975 1181
840 852

output:

12

result:

ok single line: '12'

Test #35:

score: 0
Accepted
time: 19ms
memory: 60332kb

input:

2 10 88
127 248
381 439
1812 1870
1900 1988
1332 1339
299 300
1512 1811
796 859
298 299
22 86
395 793
1041 1062

output:

11

result:

ok single line: '11'

Test #36:

score: 0
Accepted
time: 17ms
memory: 60196kb

input:

10 1 13
1186 1197
1551 1683
1725 1751
720 855
1027 1118
225 232
224 225
1849 1978
300 672
896 1017
1416 1650

output:

11

result:

ok single line: '11'

Test #37:

score: 0
Accepted
time: 17ms
memory: 60196kb

input:

10 1 147
1759 1772
973 978
1561 1632
458 773
1198 1266
139 153
987 1132
1820 1997
1157 1167
1536 1558
1875 1894

output:

10

result:

ok single line: '10'

Test #38:

score: 0
Accepted
time: 8ms
memory: 60316kb

input:

1 10 105
1601 1738
938 1059
70 108
152 194
1367 1389
1897 1912
1464 1668
1782 1847
243 338
785 845
197 209

output:

11

result:

ok single line: '11'

Test #39:

score: 0
Accepted
time: 11ms
memory: 60460kb

input:

1 10 88
1831 1885
225 342
208 210
1537 1790
1289 1290
160 197
652 661
689 776
1171 1252
1291 1459
813 870

output:

11

result:

ok single line: '11'

Test #40:

score: 0
Accepted
time: 25ms
memory: 60284kb

input:

10 10 43
1112 1136
1173 1242
196 313
1561 1603
1341 1448
428 756
1951 1989
1299 1310
1731 1919
1267 1279
1649 1682
1990 1992
295 380
883 898
15 46
1744 1784
1233 1426
1569 1603
150 173
560 723

output:

18

result:

ok single line: '18'

Test #41:

score: 0
Accepted
time: 11ms
memory: 60420kb

input:

10 10 131
1297 1299
791 825
882 968
972 1251
1293 1294
1497 1605
185 740
1460 1473
1329 1448
1861 1904
1422 1439
995 1088
1289 1321
1678 1915
372 585
760 761
1145 1170
1244 1281
16 277
765 979

output:

15

result:

ok single line: '15'

Test #42:

score: 0
Accepted
time: 8ms
memory: 60320kb

input:

10 10 286
1146 1277
224 231
302 921
1586 1708
193 201
1979 1989
999 1034
1086 1123
231 235
1058 1071
350 635
668 701
1589 1976
892 1282
1502 1568
9 22
221 295
788 867
29 89
1401 1446

output:

14

result:

ok single line: '14'

Test #43:

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

input:

10 10 99
71 108
448 470
1286 1348
1732 1966
1225 1233
1161 1174
1680 1725
480 937
109 152
223 335
1456 1465
1276 1299
1252 1254
1488 1879
101 118
159 203
1407 1437
1330 1353
898 1075
427 725

output:

15

result:

ok single line: '15'

Test #44:

score: 0
Accepted
time: 16ms
memory: 60432kb

input:

10 10 293
1260 1747
1170 1226
817 891
1763 1960
411 415
476 497
423 434
904 1096
551 716
156 323
615 630
1596 1764
133 185
384 603
1269 1371
976 1155
1156 1166
44 93
188 332
715 804

output:

11

result:

ok single line: '11'

Test #45:

score: 0
Accepted
time: 25ms
memory: 60332kb

input:

10 9 219
22 32
270 284
1291 1365
442 617
1198 1274
1624 1840
1172 1174
363 389
43 79
793 906
621 630
1788 1922
50 63
190 219
634 840
271 289
1784 1785
1111 1130
1351 1729

output:

13

result:

ok single line: '13'

Test #46:

score: 0
Accepted
time: 19ms
memory: 60324kb

input:

8 9 292
1623 1648
291 870
264 289
953 1208
1401 1587
1732 1903
1728 1732
924 938
361 475
624 825
1202 1219
1042 1119
960 1027
286 293
1252 1296
1305 1397
1769 1999

output:

11

result:

ok single line: '11'

Test #47:

score: 0
Accepted
time: 23ms
memory: 62444kb

input:

10 7 230
139 205
1593 1726
536 540
263 449
219 246
1754 1758
830 1046
1864 1873
1222 1225
1269 1421
570 649
806 818
1034 1512
443 562
820 972
1608 1901
741 775

output:

13

result:

ok single line: '13'

Test #48:

score: 0
Accepted
time: 11ms
memory: 60320kb

input:

3 5 150
501 541
1442 1596
762 992
1351 1491
1564 1635
316 361
648 1016
1180 1351

output:

7

result:

ok single line: '7'

Test #49:

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

input:

6 10 150
1710 1753
572 768
1630 1634
1638 1648
1480 1577
817 1271
7 46
687 793
87 161
1845 1973
1346 1395
1711 1810
884 1050
285 584
1458 1621
1056 1207

output:

13

result:

ok single line: '13'

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #50:

score: 10
Accepted
time: 16ms
memory: 60364kb

input:

196 2 2
903 907
1092 1095
1044 1045
1965 1973
475 483
1291 1292
1909 1913
1210 1241
195 203
1143 1144
17 25
1808 1811
1832 1834
96 104
1895 1899
1462 1473
1169 1171
280 281
860 863
174 182
756 757
1090 1092
747 752
298 299
1654 1659
850 857
59 66
320 342
909 910
130 131
1630 1632
489 490
1823 1826
1...

output:

198

result:

ok single line: '198'

Test #51:

score: 0
Accepted
time: 11ms
memory: 60348kb

input:

113 2 10
1225 1232
489 496
863 869
1316 1323
130 138
1723 1733
1792 1796
1603 1627
126 130
1601 1603
1856 1870
1561 1583
870 915
802 806
1667 1677
1167 1191
1778 1779
592 593
1840 1844
1513 1519
1542 1547
757 766
1839 1840
1677 1684
1927 1934
76 77
995 1026
1139 1140
1705 1716
635 675
1488 1493
1590...

output:

115

result:

ok single line: '115'

Test #52:

score: 0
Accepted
time: 11ms
memory: 60428kb

input:

2 180 8
1138 1978
747 987
1731 1732
1009 1010
790 809
827 828
1714 1715
375 377
166 167
57 61
700 707
634 641
1410 1415
1103 1108
963 965
395 408
594 600
64 78
1496 1505
1205 1232
1822 1828
1510 1512
53 57
996 997
1710 1714
698 699
784 786
559 560
366 375
1645 1655
517 550
113 118
1771 1778
988 991
...

output:

180

result:

ok single line: '180'

Test #53:

score: 0
Accepted
time: 16ms
memory: 60280kb

input:

2 165 7
424 885
1285 1699
1124 1125
496 497
663 671
752 756
1282 1295
569 570
732 737
346 352
1809 1810
965 975
1719 1721
407 409
912 916
100 104
333 334
357 358
1515 1530
1017 1031
1844 1849
1371 1376
413 420
1309 1321
1162 1167
1580 1583
1726 1735
1799 1803
1742 1745
317 322
309 311
253 257
157 15...

output:

167

result:

ok single line: '167'

Test #54:

score: 0
Accepted
time: 13ms
memory: 60392kb

input:

1 1 1
0 1
0 1

output:

1

result:

ok single line: '1'

Test #55:

score: 0
Accepted
time: 12ms
memory: 60584kb

input:

1 1997 2
1 2000
146 147
1863 1864
157 158
1465 1466
677 678
980 981
1692 1693
1480 1481
1270 1271
406 407
1771 1772
1686 1687
1540 1541
1879 1880
217 218
1211 1212
1002 1003
1025 1026
779 780
1963 1964
1175 1176
876 877
519 520
1791 1792
569 570
1835 1836
50 51
1393 1394
1671 1672
656 657
929 930
10...

output:

1997

result:

ok single line: '1997'

Test #56:

score: 0
Accepted
time: 16ms
memory: 60852kb

input:

999 999 1
1120 1122
988 990
1612 1614
1650 1652
1954 1956
698 700
1794 1796
420 422
406 408
1314 1316
246 248
1202 1204
22 24
766 768
1036 1038
1258 1260
1684 1686
6 8
1118 1120
1520 1522
286 288
224 226
1644 1646
144 146
594 596
1914 1916
318 320
888 890
444 446
1344 1346
1368 1370
1740 1742
708 71...

output:

1998

result:

ok single line: '1998'

Test #57:

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

input:

999 999 1
1504 1506
1374 1376
1164 1166
1306 1308
1012 1014
92 94
378 380
1240 1242
1126 1128
210 212
758 760
1626 1628
800 802
1734 1736
478 480
198 200
1256 1258
1756 1758
1678 1680
390 392
838 840
1316 1318
1100 1102
392 394
1850 1852
278 280
1296 1298
618 620
176 178
914 916
1856 1858
1450 1452
...

output:

1998

result:

ok single line: '1998'

Test #58:

score: 0
Accepted
time: 29ms
memory: 60468kb

input:

10 10 166
1660 1992
4 5
996 1328
1 2
332 664
1328 1660
2 3
0 1
664 996
3 4
334 335
1494 1826
498 830
0 332
335 336
336 337
830 1162
332 333
333 334
1162 1494

output:

20

result:

ok single line: '20'

Test #59:

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

input:

10 10 166
0 1
4 5
1328 1660
3 4
664 996
332 664
996 1328
2 3
1 2
1999 2000
830 1162
1999 2000
332 333
498 830
334 335
0 332
335 336
336 337
333 334
1162 1494

output:

19

result:

ok single line: '19'

Test #60:

score: 0
Accepted
time: 15ms
memory: 60492kb

input:

100 100 10
4 5
320 340
780 800
1340 1360
40 60
200 220
920 940
0 1
680 700
2 3
1500 1520
1040 1060
500 520
620 640
1300 1320
980 1000
140 160
1240 1260
580 600
1440 1460
60 80
180 200
520 540
7 8
1780 1800
460 480
8 9
760 780
1820 1840
1260 1280
1460 1480
1060 1080
1100 1120
1080 1100
1380 1400
3 4
...

output:

200

result:

ok single line: '200'

Test #61:

score: 0
Accepted
time: 30ms
memory: 60380kb

input:

100 100 10
840 860
20 40
320 340
1800 1820
1340 1360
240 260
300 320
7 8
220 240
140 160
400 420
1560 1580
1580 1600
200 220
1020 1040
720 740
1300 1320
260 280
340 360
1680 1700
1200 1220
120 140
1520 1540
980 1000
660 680
1140 1160
440 460
100 120
500 520
1280 1300
600 620
180 200
760 780
2 3
280 ...

output:

199

result:

ok single line: '199'

Test #62:

score: 0
Accepted
time: 20ms
memory: 60760kb

input:

1500 1500 1
1412 1413
767 768
1122 1123
1487 1488
988 989
782 783
1147 1148
298 299
343 344
433 434
1246 1247
1968 1969
1439 1441
1642 1644
799 800
1826 1827
1422 1423
873 875
903 904
1615 1616
744 745
70 71
1537 1539
1211 1212
538 539
983 984
1252 1253
865 866
1977 1978
1753 1754
803 804
998 999
55...

output:

1947

result:

ok single line: '1947'

Test #63:

score: 0
Accepted
time: 15ms
memory: 60796kb

input:

2000 2000 1000000000
212 213
428 429
1960 1961
1506 1507
1291 1292
996 997
1327 1328
168 169
1631 1632
574 575
92 93
176 177
446 447
1350 1351
506 507
1331 1332
1872 1873
198 199
1466 1467
1282 1283
1039 1040
1972 1973
1405 1406
80 81
1309 1310
389 390
224 225
1053 1054
1083 1084
814 815
258 259
13 ...

output:

2000

result:

ok single line: '2000'

Test #64:

score: 0
Accepted
time: 16ms
memory: 60572kb

input:

2000 2000 2000
1454 1455
495 496
963 964
1519 1520
1078 1079
731 732
638 639
1522 1523
1864 1865
675 676
491 492
1954 1955
1815 1816
900 901
737 738
1165 1166
1854 1855
781 782
271 272
1698 1699
637 638
623 624
1026 1027
1367 1368
714 715
9 10
291 292
397 398
214 215
318 319
1743 1744
1130 1131
1612...

output:

2000

result:

ok single line: '2000'

Test #65:

score: 0
Accepted
time: 19ms
memory: 60672kb

input:

1892 394 5
569 570
394 395
409 410
251 252
758 759
102 103
37 38
110 111
90 92
1584 1585
984 985
1110 1111
866 867
1344 1345
1362 1363
995 996
1940 1941
1504 1505
269 270
1742 1743
1891 1892
1089 1090
1692 1693
1915 1916
1626 1627
1136 1137
516 518
796 797
1139 1140
717 718
1594 1595
2 3
1085 1086
9...

output:

1892

result:

ok single line: '1892'

Test #66:

score: 0
Accepted
time: 15ms
memory: 60680kb

input:

831 1432 2
1260 1262
1030 1031
411 413
407 410
48 51
1087 1090
730 733
1268 1270
976 977
116 117
550 552
512 514
1172 1174
479 480
505 506
1117 1118
1388 1389
1699 1700
746 752
691 694
846 847
562 565
86 87
1529 1530
270 271
486 487
1443 1444
995 996
1700 1701
1943 1946
1200 1202
415 416
100 101
908...

output:

1505

result:

ok single line: '1505'

Test #67:

score: 0
Accepted
time: 22ms
memory: 60764kb

input:

1452 1660 6
843 844
1348 1349
1765 1766
1400 1401
1459 1463
1589 1590
649 650
1650 1651
655 656
50 51
1550 1551
605 606
1207 1208
1043 1044
568 569
573 574
1570 1572
1778 1779
89 90
844 845
1771 1772
899 900
1975 1976
1723 1724
1188 1189
1649 1650
1517 1518
1394 1395
330 332
1531 1532
657 658
1746 1...

output:

1658

result:

ok single line: '1658'

Test #68:

score: 0
Accepted
time: 12ms
memory: 60776kb

input:

1420 1979 3
169 171
1700 1701
363 364
1749 1751
1149 1150
414 415
441 442
40 41
1136 1137
1238 1239
429 430
267 269
1093 1094
999 1000
1979 1980
787 789
773 775
1294 1296
162 163
496 497
1408 1409
864 865
1311 1313
412 414
337 338
351 352
1887 1888
1034 1035
276 277
110 111
1717 1718
112 114
828 829...

output:

1977

result:

ok single line: '1977'

Test #69:

score: 0
Accepted
time: 24ms
memory: 60620kb

input:

1960 104 1
1525 1526
1490 1491
1385 1386
1667 1668
1050 1051
1119 1120
1339 1340
123 124
1486 1487
1645 1646
1874 1875
1307 1308
1215 1216
240 241
1464 1465
585 586
373 374
1375 1376
108 109
1718 1719
618 619
1479 1480
1394 1395
690 691
1211 1212
178 179
86 87
1361 1362
597 598
1943 1944
83 84
16 17...

output:

1974

result:

ok single line: '1974'

Test #70:

score: 0
Accepted
time: 12ms
memory: 60424kb

input:

30 67 6
1086 1141
1429 1456
1057 1058
201 204
1731 1835
1973 1987
1153 1196
596 764
338 382
1141 1151
1610 1674
1854 1941
560 575
887 892
205 269
490 501
1315 1398
894 915
1020 1031
38 75
324 334
1709 1731
1952 1970
307 323
1511 1602
94 146
951 987
384 465
1971 1973
588 592
1177 1192
1415 1480
835 8...

output:

97

result:

ok single line: '97'

Test #71:

score: 0
Accepted
time: 12ms
memory: 60268kb

input:

89 53 10
1658 1683
1766 1767
922 931
284 288
456 459
1343 1357
1609 1655
1205 1206
1806 1825
1783 1785
759 767
843 844
1195 1196
1055 1072
847 863
811 812
1507 1508
746 747
1508 1515
942 1000
1392 1401
769 774
1310 1339
1099 1101
1277 1283
891 898
1130 1134
1952 1957
1569 1570
1216 1218
813 814
621 ...

output:

130

result:

ok single line: '130'

Test #72:

score: 0
Accepted
time: 24ms
memory: 60344kb

input:

73 76 8
1108 1203
249 256
719 722
1207 1208
1540 1558
1235 1252
1422 1458
1511 1525
1685 1687
1005 1011
1687 1758
102 120
1569 1589
58 96
889 902
1078 1081
564 566
1950 1953
1357 1393
368 378
572 599
551 557
472 530
281 318
1489 1490
1878 1901
916 929
330 356
1081 1099
1312 1335
786 787
396 398
393 ...

output:

142

result:

ok single line: '142'

Test #73:

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

input:

98 98 9
784 799
1464 1471
243 289
1272 1367
1616 1618
395 446
482 497
121 134
315 336
1539 1541
2 13
160 163
339 340
1217 1258
1817 1828
1933 1945
469 471
1899 1906
1068 1069
545 552
1034 1035
343 348
1782 1785
725 727
601 611
1154 1182
143 144
1216 1217
1520 1521
1374 1386
111 112
290 307
1476 1477...

output:

176

result:

ok single line: '176'

Test #74:

score: 0
Accepted
time: 26ms
memory: 60304kb

input:

69 68 12
930 937
1114 1120
1003 1025
589 603
1091 1095
1550 1557
1379 1440
1477 1536
689 691
630 645
321 341
155 193
586 587
1037 1048
531 574
519 522
1815 1824
1614 1621
377 378
782 789
1915 1943
1265 1289
1992 1996
1122 1168
1358 1361
1623 1653
1986 1988
1678 1707
114 118
1226 1227
64 68
754 757
6...

output:

121

result:

ok single line: '121'

Test #75:

score: 0
Accepted
time: 24ms
memory: 60500kb

input:

1352 183 39
236 238
1924 1925
225 226
1931 1932
1129 1130
1944 1945
490 491
1669 1670
710 711
1137 1138
804 805
134 135
821 822
78 79
200 201
240 241
1159 1161
447 448
274 277
253 255
792 793
1789 1790
1407 1408
326 327
300 301
238 239
1185 1186
1568 1569
1062 1063
13 14
1889 1890
1345 1346
829 831
...

output:

1352

result:

ok single line: '1352'

Test #76:

score: 0
Accepted
time: 13ms
memory: 60828kb

input:

1430 1017 82
575 576
520 521
1993 1995
446 447
1388 1389
1397 1398
459 460
909 911
373 374
120 121
1587 1588
1286 1287
1623 1624
1704 1705
464 467
494 495
848 850
995 996
72 73
1073 1074
394 395
1114 1116
1175 1176
399 400
712 713
1122 1123
1868 1870
1747 1748
415 416
125 126
1177 1178
1284 1285
715...

output:

1430

result:

ok single line: '1430'

Test #77:

score: 0
Accepted
time: 16ms
memory: 60872kb

input:

1363 1894 59
1183 1185
1225 1226
1764 1765
348 349
511 512
1831 1832
401 403
1835 1836
1307 1308
1403 1404
899 901
368 369
132 133
1739 1741
307 308
1269 1270
883 884
1962 1963
1689 1690
1649 1650
78 79
746 747
1401 1402
49 50
1977 1979
620 621
1613 1614
1780 1781
1874 1876
1678 1679
546 547
541 543...

output:

1839

result:

ok single line: '1839'

Test #78:

score: 0
Accepted
time: 18ms
memory: 60696kb

input:

1267 1698 84
686 690
328 329
294 295
145 146
311 312
1551 1552
338 339
1195 1196
92 93
1186 1187
1552 1553
1360 1361
190 192
1673 1674
804 805
867 870
1834 1835
610 611
1508 1510
1170 1171
970 972
920 921
239 240
1234 1237
1014 1016
291 292
1343 1345
634 635
173 174
604 605
1634 1635
1217 1218
177 1...

output:

1632

result:

ok single line: '1632'

Test #79:

score: 0
Accepted
time: 13ms
memory: 60640kb

input:

605 1673 97
1840 1842
452 453
1979 1981
1709 1711
1087 1089
962 965
955 957
1954 1955
1614 1615
694 695
1031 1032
1569 1570
1246 1247
810 811
62 71
1050 1051
935 939
1355 1356
165 173
1922 1923
360 361
331 332
1736 1738
1973 1976
570 571
1824 1826
546 547
801 802
800 801
1616 1618
159 160
34 38
349 ...

output:

1591

result:

ok single line: '1591'

Test #80:

score: 0
Accepted
time: 21ms
memory: 60608kb

input:

244 623 615
1867 1875
546 551
515 517
1329 1331
1383 1387
1895 1896
1324 1328
1417 1418
1906 1909
654 657
908 912
837 838
1811 1816
1465 1466
455 457
146 147
208 219
447 449
147 148
229 232
381 382
1865 1866
366 370
1362 1363
1136 1137
138 143
1630 1636
436 446
761 771
954 961
1336 1345
1169 1171
13...

output:

427

result:

ok single line: '427'

Test #81:

score: 0
Accepted
time: 29ms
memory: 60760kb

input:

1348 1771 1013
496 497
528 530
1547 1548
1937 1938
149 150
475 477
1083 1084
1640 1641
756 757
1299 1300
682 684
1273 1274
952 953
57 58
376 379
748 749
211 213
757 758
1831 1832
1103 1104
1401 1403
609 612
161 162
880 882
1191 1192
1803 1804
479 481
445 446
1941 1942
999 1000
1317 1318
711 712
1629...

output:

1348

result:

ok single line: '1348'

Test #82:

score: 0
Accepted
time: 30ms
memory: 60628kb

input:

1670 458 1539
1103 1104
1526 1527
505 506
1204 1206
158 160
1486 1487
115 117
295 296
921 922
348 349
1260 1261
1072 1073
1330 1331
361 362
1977 1978
1161 1162
57 58
1164 1165
317 318
1216 1217
703 704
1558 1559
1922 1923
236 237
1735 1736
1343 1344
1383 1384
1090 1091
1437 1438
1600 1601
1664 1665
...

output:

1670

result:

ok single line: '1670'

Test #83:

score: 0
Accepted
time: 18ms
memory: 60764kb

input:

1762 1392 901
1002 1003
263 264
1437 1438
1151 1152
328 329
1265 1266
666 667
1605 1606
505 506
104 105
1205 1206
1600 1601
1622 1623
1954 1955
1493 1494
1257 1258
189 190
1795 1796
1224 1225
273 274
1161 1162
1857 1859
899 901
642 643
975 976
876 877
1191 1192
1556 1557
73 74
121 122
1302 1303
1508...

output:

1762

result:

ok single line: '1762'

Test #84:

score: 0
Accepted
time: 8ms
memory: 60612kb

input:

421 1458 1384
1820 1821
1094 1101
263 264
862 876
842 845
585 586
26 27
275 279
1448 1449
693 694
1045 1046
1745 1758
1958 1960
1225 1228
1819 1820
43 53
268 269
1835 1837
408 413
1997 1999
1981 1984
415 418
1536 1542
407 408
664 667
1730 1734
1317 1321
431 438
1495 1496
1711 1714
1149 1150
1592 159...

output:

463

result:

ok single line: '463'

Test #85:

score: 0
Accepted
time: 19ms
memory: 60504kb

input:

161 254 735063421
1501 1506
1971 1987
1592 1614
1063 1067
1107 1120
1784 1789
1968 1970
181 217
1463 1468
962 966
1569 1572
418 424
677 682
1475 1478
937 942
1351 1356
1619 1622
1450 1455
224 229
76 90
1837 1838
1795 1796
1196 1201
1566 1567
905 924
658 659
798 805
1987 1991
1825 1835
1483 1492
660 ...

output:

161

result:

ok single line: '161'

Test #86:

score: 0
Accepted
time: 11ms
memory: 60192kb

input:

1 1 1000000000
1694 1724
517 619

output:

1

result:

ok single line: '1'

Test #87:

score: 0
Accepted
time: 15ms
memory: 60332kb

input:

1 1 476
69 1093
476 1675

output:

2

result:

ok single line: '2'

Test #88:

score: 0
Accepted
time: 21ms
memory: 60312kb

input:

1 1 1688
1427 1575
580 688

output:

1

result:

ok single line: '1'

Test #89:

score: 0
Accepted
time: 13ms
memory: 60244kb

input:

1 1 1511
362 1076
1479 1635

output:

1

result:

ok single line: '1'

Test #90:

score: 0
Accepted
time: 15ms
memory: 60416kb

input:

1 1 1113
1559 1647
1199 1418

output:

1

result:

ok single line: '1'

Test #91:

score: 0
Accepted
time: 21ms
memory: 60320kb

input:

2 2 823
1014 1097
50 762
1668 1730
997 1239

output:

3

result:

ok single line: '3'

Test #92:

score: 0
Accepted
time: 28ms
memory: 60248kb

input:

2 2 550
814 1312
11 356
43 1066
1300 1569

output:

3

result:

ok single line: '3'

Test #93:

score: 0
Accepted
time: 8ms
memory: 60288kb

input:

2 2 1941
1838 1871
1174 1270
168 174
210 1967

output:

2

result:

ok single line: '2'

Test #94:

score: 0
Accepted
time: 11ms
memory: 60328kb

input:

2 2 1349
1017 1521
17 112
634 1547
491 610

output:

2

result:

ok single line: '2'

Test #95:

score: 0
Accepted
time: 8ms
memory: 60276kb

input:

300 300 9
1677 1678
197 205
583 584
681 684
398 401
485 486
1074 1077
1594 1598
1509 1513
886 887
1323 1329
952 967
1864 1866
531 532
14 20
768 783
534 541
602 605
1713 1725
1553 1555
266 269
1121 1132
1036 1044
1777 1780
639 643
433 436
1663 1670
938 942
1204 1205
1185 1190
1592 1594
1309 1310
887 ...

output:

403

result:

ok single line: '403'

Test #96:

score: 0
Accepted
time: 21ms
memory: 60408kb

input:

300 300 10
606 608
778 780
1732 1733
269 270
630 633
1536 1537
219 221
1022 1023
1235 1238
950 954
922 923
339 341
1688 1693
319 322
215 218
1553 1557
1135 1142
1435 1448
986 996
408 422
1024 1029
272 278
512 519
141 144
1112 1115
800 806
3 5
1254 1256
48 49
682 684
914 917
1979 1981
824 835
1744 17...

output:

384

result:

ok single line: '384'

Test #97:

score: 0
Accepted
time: 11ms
memory: 60336kb

input:

300 300 4
642 643
1297 1300
1906 1908
391 392
527 528
1647 1648
1285 1288
1466 1473
912 920
1087 1089
90 92
55 56
396 398
181 188
617 621
922 923
153 156
1605 1607
1499 1512
1446 1448
1866 1869
932 933
11 15
1162 1166
319 320
856 857
228 229
1777 1778
1304 1312
1218 1228
765 769
653 656
1857 1863
17...

output:

491

result:

ok single line: '491'

Test #98:

score: 0
Accepted
time: 15ms
memory: 60424kb

input:

300 300 6
411 412
427 428
1127 1128
907 909
420 421
1416 1417
906 907
636 639
1920 1931
921 934
171 176
1761 1767
1061 1063
248 254
1363 1368
635 636
597 599
1089 1090
974 997
1847 1858
105 107
1111 1113
1513 1527
1102 1108
1003 1022
920 921
1401 1404
1733 1735
108 109
945 947
1068 1070
366 373
1317...

output:

445

result:

ok single line: '445'

Test #99:

score: 0
Accepted
time: 8ms
memory: 60396kb

input:

300 300 7
916 918
978 981
1159 1160
86 91
654 655
442 448
1227 1235
678 679
471 472
612 614
598 600
1544 1548
1139 1140
1440 1452
540 542
823 825
608 609
1768 1769
1053 1054
201 203
640 653
1203 1206
847 848
892 904
1070 1078
253 256
858 861
1939 1950
792 798
812 816
557 562
1936 1937
1056 1059
1846...

output:

422

result:

ok single line: '422'

Test #100:

score: 0
Accepted
time: 21ms
memory: 60316kb

input:

196 1 2
136 137
112 113
81 83
978 980
1842 1843
1259 1260
1845 1847
507 516
1252 1253
818 846
973 974
1471 1482
1369 1376
209 210
1539 1540
1278 1282
1574 1577
59 64
1284 1290
918 919
1918 1919
893 894
1619 1626
641 644
1813 1818
464 468
1548 1553
647 648
846 854
670 690
604 609
854 867
1051 1070
92...

output:

197

result:

ok single line: '197'

Test #101:

score: 0
Accepted
time: 21ms
memory: 60348kb

input:

113 1 10
844 860
1656 1668
1446 1447
992 1029
949 971
277 287
1790 1803
1706 1714
574 582
115 201
1724 1732
1669 1671
1366 1399
204 208
712 713
1269 1356
527 528
823 834
1149 1167
1811 1833
467 469
1522 1524
528 534
1445 1446
256 261
899 905
777 804
1527 1529
917 942
1693 1700
733 770
658 673
1776 1...

output:

114

result:

ok single line: '114'

Test #102:

score: 0
Accepted
time: 17ms
memory: 60324kb

input:

1 180 8
589 1300
422 423
1140 1148
1762 1777
1971 1972
568 569
231 234
904 905
912 925
1151 1158
695 697
281 290
350 356
847 850
599 600
1355 1357
790 793
702 704
1548 1557
1197 1200
700 701
1357 1361
251 261
312 316
817 835
1041 1042
1079 1099
838 844
1363 1366
1932 1936
1212 1216
1506 1509
1010 10...

output:

181

result:

ok single line: '181'

Test #103:

score: 0
Accepted
time: 16ms
memory: 60308kb

input:

1 165 7
67 1996
1539 1541
646 647
1920 1927
1458 1484
1361 1368
1732 1734
1658 1664
1604 1626
1634 1642
191 194
931 938
1685 1687
564 572
1288 1310
275 281
457 465
85 93
245 247
914 915
1497 1505
1484 1485
379 383
647 650
626 636
1804 1819
1768 1775
615 623
1969 1973
1011 1017
738 763
1741 1743
214 ...

output:

165

result:

ok single line: '165'

Subtask #3:

score: 6
Accepted

Test #104:

score: 6
Accepted
time: 8ms
memory: 60280kb

input:

1 1 1
0 1
0 1

output:

1

result:

ok single line: '1'

Test #105:

score: 0
Accepted
time: 24ms
memory: 60572kb

input:

1 2000 2
999999996 1000000000
336 337
502 503
1906 1907
963 964
1351 1352
1795 1796
1510 1511
304 305
1930 1931
1735 1736
1469 1470
338 339
813 814
182 183
209 210
321 322
849 850
721 722
394 395
889 890
1758 1759
1440 1441
560 561
1470 1471
1916 1917
793 794
1366 1367
158 159
1602 1603
214 215
1119...

output:

2000

result:

ok single line: '2000'

Test #106:

score: 0
Accepted
time: 16ms
memory: 61572kb

input:

2000 2000 249875
608195750 608695500
88455750 88955500
579210250 579710000
817091250 817591000
527736000 528235750
52473750 52973500
89955000 90454750
184407750 184907500
668165750 668665500
24487750 24987500
466266750 466766500
471764000 472263750
212393750 212893500
250874500 251374250
939530000 9...

output:

4000

result:

ok single line: '4000'

Test #107:

score: 0
Accepted
time: 8ms
memory: 61648kb

input:

2000 2000 249875
965017250 965517000
73963000 74462750
242878500 243378250
148925500 149425250
747126250 747626000
384307750 384807500
655172250 655672000
278360750 278860500
899050250 899550000
496251750 496751500
92953500 93453250
677661000 678160750
828085750 828585500
297351250 297851000
5887055...

output:

4000

result:

ok single line: '4000'

Test #108:

score: 0
Accepted
time: 27ms
memory: 61340kb

input:

2000 2000 499500
428 429
764235000 765234000
511488000 512487000
291 292
585414000 586413000
127 128
819 820
727 728
233766000 234765000
643 644
234 235
326 327
432 433
218781000 219780000
10989000 11988000
805194000 806193000
283716000 284715000
965034000 966033000
632367000 633366000
824 825
454 4...

output:

4000

result:

ok single line: '4000'

Test #109:

score: 0
Accepted
time: 19ms
memory: 61168kb

input:

2000 2000 499500
175 176
766233000 767232000
230 231
925 926
844 845
681318000 682317000
48951000 49950000
757 758
266 267
438561000 439560000
262737000 263736000
813 814
915084000 916083000
485514000 486513000
214785000 215784000
532467000 533466000
25 26
41958000 42957000
534 535
331 332
53 54
732...

output:

3999

result:

ok single line: '3999'

Test #110:

score: 0
Accepted
time: 13ms
memory: 60660kb

input:

2000 2000 1
97918740 97918742
612788646 612788648
709014683 709014684
550596486 550596488
611820813 611820815
742133170 742133172
999593290 999593292
65695562 65695563
984598976 984598977
285428771 285428773
334881813 334881814
751309389 751309390
635034524 635034526
202056719 202056720
472216430 47...

output:

4000

result:

ok single line: '4000'

Test #111:

score: 0
Accepted
time: 15ms
memory: 60688kb

input:

2000 2000 1000000000
762582513 763402869
685982674 685994777
607586653 607621748
725505868 725606928
287661547 287711487
961278566 961422544
282891861 282922769
388240582 388471546
305173664 305545845
17696180 17939334
267223086 267237726
251362344 251735629
957622587 957813570
321979347 321992100
7...

output:

2000

result:

ok single line: '2000'

Test #112:

score: 0
Accepted
time: 16ms
memory: 60712kb

input:

2000 2000 1000000000
675 676
1250 1251
1565 1566
211 212
951 952
250 251
1975 1976
775 776
795 796
85 86
212 213
293 294
1970 1971
627 628
1945 1946
688 689
1050 1051
223 224
288 289
476 477
137 138
613 614
1400 1401
1087 1088
801 802
734 735
1112 1113
51 52
1127 1128
546 547
881 882
276 277
680 681...

output:

2000

result:

ok single line: '2000'

Test #113:

score: 0
Accepted
time: 15ms
memory: 60800kb

input:

2000 2000 2000
683 684
170 171
1005 1006
1612 1613
330 331
280 281
1340 1341
1083 1084
355 356
1603 1604
1001 1002
873 874
1520 1521
1657 1658
1827 1828
1868 1869
655 656
1981 1982
184 185
900 901
1917 1918
1096 1097
956 957
987 988
536 537
921 922
317 318
869 870
1095 1096
1684 1685
762 763
1896 18...

output:

2000

result:

ok single line: '2000'

Test #114:

score: 0
Accepted
time: 16ms
memory: 60540kb

input:

89 1537 3
1761 1764
1885 1887
1489 1490
1523 1528
1491 1494
1204 1206
288 293
1433 1439
233 235
1007 1009
1630 1635
1297 1301
359 363
1559 1561
1918 1922
1160 1161
1374 1377
418 420
248 252
1826 1831
1051 1053
720 722
276 279
1516 1522
1638 1639
28 34
1392 1394
1867 1869
1030 1035
961 964
951 954
56...

output:

1538

result:

ok single line: '1538'

Test #115:

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

input:

1530 1057 6
333 334
1671 1672
855 856
237 238
429 430
172 173
1721 1722
784 785
485 486
771 772
1563 1564
781 784
852 854
510 511
754 755
1640 1641
1748 1749
152 153
1286 1287
1765 1766
483 484
1374 1375
1435 1436
1081 1082
1960 1961
1512 1513
1001 1002
1287 1288
1737 1738
1213 1214
901 902
271 272
...

output:

1530

result:

ok single line: '1530'

Test #116:

score: 0
Accepted
time: 19ms
memory: 60676kb

input:

1852 95 2
1686 1687
1089 1090
1406 1407
1703 1704
270 271
124 125
1656 1657
1467 1468
1244 1245
198 199
720 721
240 241
954 955
1617 1618
1576 1577
693 694
887 888
1875 1876
65 66
210 211
972 973
60 61
1977 1978
1747 1748
88 89
1571 1572
1913 1914
959 960
978 979
1592 1593
160 161
911 912
1923 1924
...

output:

1852

result:

ok single line: '1852'

Test #117:

score: 0
Accepted
time: 26ms
memory: 60780kb

input:

2000 2000 8
113542287 113542302
390186210 390186213
767610940 767610945
166969613 166969625
576186044 576186049
900919537 900919544
65847079 65847093
914274569 914274570
717871869 717871873
446375619 446375623
411070467 411070470
118697002 118697012
686550784 686550796
825791725 825791731
986657892 ...

output:

4000

result:

ok single line: '4000'

Test #118:

score: 0
Accepted
time: 19ms
memory: 60712kb

input:

2000 2000 5
323112971 323112977
625095129 625095132
724765420 724765421
63941016 63941019
914151487 914151492
984437587 984437595
208379851 208379858
839949614 839949623
928366669 928366671
561458859 561458867
972589960 972589964
576223356 576223364
739171385 739171390
663662925 663662932
525889027 ...

output:

4000

result:

ok single line: '4000'

Test #119:

score: 0
Accepted
time: 16ms
memory: 60712kb

input:

2000 2000 6
298171660 298171662
490725349 490725356
36304805 36304811
207802050 207802060
837587473 837587479
987183666 987183676
560955022 560955034
287590452 287590463
694565254 694565264
859529266 859529272
541494910 541494922
771349806 771349812
225787473 225787476
648584932 648584944
905255077 ...

output:

4000

result:

ok single line: '4000'

Test #120:

score: 0
Accepted
time: 16ms
memory: 60768kb

input:

1641 1376 22
377 378
697 698
693 694
210 211
1214 1216
1345 1346
846 847
1532 1533
1935 1937
1069 1070
1597 1598
318 319
1066 1067
886 887
1302 1303
1103 1105
631 632
1787 1788
1063 1064
1152 1154
227 228
351 352
1718 1719
754 755
238 239
651 652
704 705
601 602
1332 1333
1945 1946
421 422
1392 1393...

output:

1641

result:

ok single line: '1641'

Test #121:

score: 0
Accepted
time: 8ms
memory: 60568kb

input:

718 741 39
1263 1273
1019 1020
1202 1205
1105 1106
1194 1195
459 463
548 550
1821 1825
1853 1854
1664 1665
831 832
26 27
705 706
1832 1833
1466 1467
1438 1439
1841 1842
590 591
1981 1983
1310 1314
1850 1853
1978 1980
1948 1949
993 994
743 746
702 704
1748 1751
956 957
536 539
1694 1696
653 654
54 55...

output:

735

result:

ok single line: '735'

Test #122:

score: 0
Accepted
time: 8ms
memory: 60732kb

input:

1375 1578 67
427 428
14 15
1981 1982
1983 1984
1865 1866
1425 1426
1944 1945
1796 1798
1045 1046
705 706
870 871
184 185
1817 1818
591 592
1710 1711
1132 1133
782 783
902 903
1805 1806
1438 1439
1508 1510
620 621
1832 1833
594 596
1471 1472
645 646
432 434
1680 1681
8 9
1318 1319
1543 1544
977 978
1...

output:

1532

result:

ok single line: '1532'

Test #123:

score: 0
Accepted
time: 23ms
memory: 60804kb

input:

2000 2000 22
341868816 341868843
367155688 367155695
135493529 135493570
659841251 659841280
765819862 765819872
784722731 784722769
141544674 141544697
616625335 616625350
476905250 476905273
242349445 242349486
939296167 939296190
296381442 296381478
528751822 528751862
608293329 608293356
5822529...

output:

4000

result:

ok single line: '4000'

Test #124:

score: 0
Accepted
time: 24ms
memory: 60692kb

input:

2000 2000 39
927916622 927916697
325367766 325367794
856736217 856736254
536269830 536269853
10213264 10213320
525742332 525742365
286222090 286222105
967547156 967547227
725030525 725030576
934264787 934264801
572638578 572638600
236729969 236730024
628968602 628968676
100517630 100517639
985987837...

output:

4000

result:

ok single line: '4000'

Test #125:

score: 0
Accepted
time: 8ms
memory: 60664kb

input:

2000 2000 67
767187100 767187119
986940990 986941073
308695512 308695622
238031183 238031199
754701671 754701748
2519007 2519037
847920995 847921121
867519831 867519887
633569931 633570037
21505154 21505229
541253140 541253210
76904813 76904931
370362036 370362147
222364602 222364689
643428933 64342...

output:

4000

result:

ok single line: '4000'

Test #126:

score: 0
Accepted
time: 26ms
memory: 60760kb

input:

1801 1118 7
5008 5011
9388 9394
5853 5858
8470 8471
1273 1275
968 970
1583 1585
6999 7000
6626 6632
1362 1365
546 551
4540 4541
5756 5757
3236 3238
7883 7886
3451 3458
1186 1188
3646 3654
8632 8633
1676 1677
9121 9122
4981 4983
4869 4870
3329 3333
7979 7980
322 325
9441 9443
2033 2035
741 742
7317 7...

output:

2095

result:

ok single line: '2095'

Test #127:

score: 0
Accepted
time: 12ms
memory: 60632kb

input:

173 1328 4
6361 6362
8758 8760
1604 1612
5366 5368
3091 3099
8362 8367
8399 8406
2915 2920
1585 1591
9754 9758
5517 5525
5508 5510
5816 5823
3670 3672
3244 3245
7414 7418
1843 1845
9671 9679
2922 2926
9643 9645
2708 2712
5000 5003
180 181
1151 1152
5945 5950
6430 6435
8478 8481
4595 4603
1084 1090
2...

output:

1444

result:

ok single line: '1444'

Test #128:

score: 0
Accepted
time: 20ms
memory: 60632kb

input:

1344 1104 5
1879 1884
8042 8044
1512 1514
9729 9736
2229 2232
9974 9975
4335 4339
3631 3634
4816 4817
5661 5662
6275 6280
8797 8804
6347 6348
9244 9245
5884 5885
2314 2316
4341 4350
1109 1110
8190 8199
3209 3210
2266 2267
7240 7241
442 444
1650 1660
8626 8632
6517 6522
3564 3565
7379 7380
54 55
9592...

output:

1968

result:

ok single line: '1968'

Test #129:

score: 0
Accepted
time: 17ms
memory: 60504kb

input:

1801 1118 8818
299648146 299648921
634991862 634995510
17600292 17606666
584960465 584975652
605178662 605188921
136825738 136830581
468470295 468487515
812289237 812291890
908300607 908301000
371061746 371065020
637916467 637921315
791509404 791516878
579815394 579830764
165461681 165471358
3709745...

output:

2914

result:

ok single line: '2914'

Test #130:

score: 0
Accepted
time: 22ms
memory: 60568kb

input:

173 1328 504
789591864 789592603
419389263 419389465
631057151 631057560
793894508 793894560
733337608 733337946
347331803 347332760
406894159 406894174
377922914 377923695
850278166 850278984
966882383 966882891
40040418 40040511
431425356 431425613
339847101 339847278
661365924 661366278
20859765 ...

output:

1501

result:

ok single line: '1501'

Test #131:

score: 0
Accepted
time: 15ms
memory: 60724kb

input:

2000 2000 7984
339920481 339921279
225025481 225031390
368905241 368910451
859123005 859134183
229280199 229288499
13788323 13790692
454496099 454506465
705349718 705362443
312435440 312441025
471001714 471011731
583513429 583522612
828898408 828903187
337955186 337963628
546809371 546812177
9662249...

output:

3991

result:

ok single line: '3991'

Test #132:

score: 0
Accepted
time: 16ms
memory: 60652kb

input:

1477 1013 215799
820746965 820903972
235759939 235964519
927350766 927372711
441613567 441617616
223651883 223808949
451588249 451780490
537058997 537297402
980442214 980652302
339359130 339380069
814950455 815096407
123458370 123552031
577757858 578074582
209150551 209286637
679146135 679265919
862...

output:

2313

result:

ok single line: '2313'

Test #133:

score: 0
Accepted
time: 24ms
memory: 60552kb

input:

690 1275 103826
69978534 70044833
362562070 362617101
138568866 138737780
100792091 100903864
806054798 806210315
303203756 303214371
365107745 365189852
331126421 331275613
905525891 905527125
797188174 797320999
751853571 751990547
781606965 781665188
936696124 936808636
64417551 64428684
81940041...

output:

1927

result:

ok single line: '1927'

Test #134:

score: 0
Accepted
time: 21ms
memory: 60636kb

input:

2000 2000 238104
396195086 396200531
847207834 847332258
179994708 180280134
936637373 936637803
142798890 143169794
485081815 485105422
980224150 980253706
746341763 746420525
58384006 58500295
825594403 825910834
86660443 86662952
129714220 129807587
985730074 985738891
492676441 492860827
8601734...

output:

3429

result:

ok single line: '3429'

Test #135:

score: 0
Accepted
time: 23ms
memory: 60720kb

input:

2000 2000 840413426
245432126 245840266
820710817 821104962
399672634 399941306
193464621 193504820
22371266 22467427
208469456 208657256
243779942 243908247
598840393 598869355
485615359 486254153
22892035 23841416
822113439 822724655
429404275 429512297
422467661 423173061
347293788 347392975
8087...

output:

2000

result:

ok single line: '2000'

Test #136:

score: 0
Accepted
time: 8ms
memory: 60332kb

input:

1 1 1000000000
516542443 729841337
244428434 812275082

output:

1

result:

ok single line: '1'

Test #137:

score: 0
Accepted
time: 15ms
memory: 60312kb

input:

1 1 157846707
475798536 565048510
925017069 932822770

output:

2

result:

ok single line: '2'

Test #138:

score: 0
Accepted
time: 11ms
memory: 60312kb

input:

1 1 950798221
8782268 789153107
355263574 830913501

output:

1

result:

ok single line: '1'

Test #139:

score: 0
Accepted
time: 8ms
memory: 60460kb

input:

1 1 671388450
295587077 322796253
196014814 610531728

output:

1

result:

ok single line: '1'

Test #140:

score: 0
Accepted
time: 11ms
memory: 60192kb

input:

1 1 364785590
947989275 956495485
802397137 931606382

output:

1

result:

ok single line: '1'

Test #141:

score: 0
Accepted
time: 16ms
memory: 60320kb

input:

2 2 731145322
187729013 483416577
713971619 873645695
713631432 745397721
531149064 619687775

output:

2

result:

ok single line: '2'

Test #142:

score: 0
Accepted
time: 19ms
memory: 60324kb

input:

2 2 118961482
393921001 484808236
28918989 201556545
827862893 859953290
21806393 82884525

output:

3

result:

ok single line: '3'

Test #143:

score: 0
Accepted
time: 11ms
memory: 60332kb

input:

2 2 866022286
346503962 854690942
978283256 989458723
307988586 359532820
388575756 847032394

output:

2

result:

ok single line: '2'

Test #144:

score: 0
Accepted
time: 12ms
memory: 60420kb

input:

2 2 579190821
696013116 862318605
920027096 948189287
34511307 349337089
688888024 865627719

output:

2

result:

ok single line: '2'

Test #145:

score: 0
Accepted
time: 20ms
memory: 60652kb

input:

2000 2000 28457
380073308 380129124
337673316 337725490
328507761 328512801
80835174 80886619
506386553 506409956
449767860 449804796
729249984 729266202
280195213 280251651
309921700 309949789
168590985 168645214
553950166 553982841
870386267 870388775
841632890 841661301
115503002 115538714
623851...

output:

3953

result:

ok single line: '3953'

Test #146:

score: 0
Accepted
time: 14ms
memory: 60876kb

input:

2000 2000 256401
674503522 674530800
507904838 508414477
713869060 714061164
411783621 412081838
34060885 34255407
244482303 244549640
374806533 374863581
107557985 107939331
931987804 932274196
384456654 384494772
996331844 996356706
720269743 720570553
878985719 879227913
494035573 494213734
12066...

output:

3371

result:

ok single line: '3371'

Test #147:

score: 0
Accepted
time: 12ms
memory: 60760kb

input:

2000 2000 191323
608483839 608548210
440584583 440731206
122944325 123104690
994111553 994263026
522856060 522890155
219442124 219501599
8538966 8748323
949304216 949393487
177315835 177451353
314313734 314353881
407881410 408029302
962479115 962589734
498940105 498941336
735093209 735095084
7376835...

output:

3548

result:

ok single line: '3548'

Test #148:

score: 0
Accepted
time: 21ms
memory: 60624kb

input:

2000 2000 82111
815001816 815076652
646244157 646361382
62945198 63100281
651403764 651517305
330022446 330156800
557602579 557650791
203637679 203742643
936537983 936662233
362156394 362300631
621507302 621507982
553311750 553444349
500235685 500240539
817919163 818009223
334919155 334930575
925197...

output:

3821

result:

ok single line: '3821'

Test #149:

score: 0
Accepted
time: 19ms
memory: 60768kb

input:

2000 2000 294760
571769883 571829761
768941839 768970823
763555200 763829761
616413956 616589623
753061171 753081450
855737523 855781281
996835306 997129662
374495408 375047231
734657466 734703873
987347700 987354200
818298781 818367789
725716484 725749323
424315835 424369262
22593232 22911537
33207...

output:

3291

result:

ok single line: '3291'

Test #150:

score: 0
Accepted
time: 16ms
memory: 60564kb

input:

1525 2 5
1126 1127
1476 1477
72 73
139 140
1914 1915
1620 1622
1026 1027
1538 1540
1128 1129
288 289
866 867
1373 1374
101 102
1723 1724
57 58
1268 1269
1225 1226
1283 1284
1618 1619
1855 1856
1059 1061
1514 1515
197 198
912 913
165 166
1739 1740
1262 1263
650 652
1007 1008
1093 1094
1964 1965
1241 ...

output:

1525

result:

ok single line: '1525'

Test #151:

score: 0
Accepted
time: 21ms
memory: 60564kb

input:

1702 2 4
1548 1549
904 905
1343 1344
1347 1348
803 804
748 749
980 981
940 941
1596 1597
435 436
392 393
1621 1622
492 495
1613 1614
1193 1194
1254 1255
1728 1729
1453 1454
602 603
721 722
1051 1052
517 519
1094 1095
1389 1390
1175 1176
737 738
383 384
796 797
1048 1049
364 365
1243 1244
77 78
698 6...

output:

1702

result:

ok single line: '1702'

Test #152:

score: 0
Accepted
time: 16ms
memory: 60668kb

input:

2 1842 5
1649 1658
974 980
716 717
629 630
923 924
401 402
767 768
1083 1084
1715 1716
566 567
1474 1475
453 454
1406 1407
986 987
1227 1228
1935 1936
1115 1116
1692 1693
606 607
1680 1681
1220 1221
46 47
180 181
912 913
1523 1524
84 85
1669 1670
943 944
301 302
1067 1068
1267 1268
734 735
292 293
5...

output:

1837

result:

ok single line: '1837'

Test #153:

score: 0
Accepted
time: 27ms
memory: 60572kb

input:

2 1713 9
692 710
1376 1386
546 547
1873 1874
1936 1939
609 610
728 729
293 294
1204 1205
19 20
684 685
624 625
1328 1329
924 925
1427 1430
1032 1033
205 206
1002 1003
1949 1950
731 732
1811 1812
1156 1157
1813 1814
889 890
216 217
353 355
1407 1408
77 78
974 975
1175 1176
181 182
294 296
1709 1710
1...

output:

1705

result:

ok single line: '1705'

Test #154:

score: 0
Accepted
time: 9ms
memory: 60500kb

input:

2000 1 108105
187921009 187961418
592143747 592188599
922359958 922389775
988218771 988225408
8987087 8987717
536625603 536800134
401048877 401109194
249177840 249246564
357945322 358109360
557958363 558045049
990977821 991071233
212404154 212559055
677302708 677425620
664040131 664070755
575580713 ...

output:

2001

result:

ok single line: '2001'

Test #155:

score: 0
Accepted
time: 24ms
memory: 60448kb

input:

2000 1 42043
248418289 248428903
262126576 262205880
341350718 341398710
687842074 687898478
208756003 208813352
841401287 841479136
321618143 321651701
145758063 145790503
830388644 830466424
291322130 291348904
890589266 890637660
841317532 841326868
396230807 396306490
543127945 543152517
3496195...

output:

2001

result:

ok single line: '2001'

Test #156:

score: 0
Accepted
time: 23ms
memory: 60676kb

input:

1 2000 21109
410539256 410552084
67989547 68015733
200370296 200395275
396926722 396944106
460851522 460877196
599593879 599607906
712048365 712082364
184484773 184501074
928903952 928927650
259836807 259849794
839108299 839132147
85792178 85817583
607464562 607491353
983862486 983898379
564750183 5...

output:

2001

result:

ok single line: '2001'

Test #157:

score: 0
Accepted
time: 15ms
memory: 60572kb

input:

1 2000 86622
2358374 2400270
547874758 548008800
912368307 912373746
997351820 997510394
408371119 408386094
598559013 598686260
354218449 354243412
646881698 646885986
827317851 827328126
418036216 418196733
496893855 497005209
569270016 569283311
974971433 974999605
538145213 538156103
434650974 4...

output:

2001

result:

ok single line: '2001'

Test #158:

score: 0
Accepted
time: 20ms
memory: 60452kb

input:

2000 2 108105
751875900 752063445
479603128 479723048
959440486 959471902
947706899 947735691
838210907 838323807
668707993 668726918
433531215 433634779
38163172 38182709
937028255 937228183
81985312 82104130
629601403 629751775
580639862 580684122
307720738 307821298
795422201 795511331
75530227 7...

output:

2002

result:

ok single line: '2002'

Test #159:

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

input:

2000 2 42043
160299579 160328221
809717057 809765069
849291898 849310443
287886469 287887321
962137052 962150020
876001134 876058843
249869760 249873039
378206736 378231376
351804265 351854400
925643833 925698925
990354844 990397870
246783917 246787369
894065905 894117294
390109027 390125953
8786664...

output:

2002

result:

ok single line: '2002'

Test #160:

score: 0
Accepted
time: 12ms
memory: 60544kb

input:

2 2000 21109
232242567 232279657
181892166 181893450
256124895 256141502
651831545 651868563
991862053 991895038
702176857 702183773
180105182 180129094
150378798 150384642
831861630 831881627
674419850 674447245
957088026 957113714
230393422 230401087
548338273 548364231
526354591 526366218
4870647...

output:

2002

result:

ok single line: '2002'

Test #161:

score: 0
Accepted
time: 16ms
memory: 60576kb

input:

2 2000 86622
678837493 678857835
824310222 824325939
90356938 90436703
742962791 743105103
74825982 74941113
100503880 100514658
730002495 730029639
278886175 279024478
98961053 99114685
585620816 585747332
571685115 571779160
793720942 793740112
670270680 670438626
761673044 761773765
388050017 388...

output:

2002

result:

ok single line: '2002'

Subtask #4:

score: 4
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #162:

score: 4
Accepted
time: 16ms
memory: 60428kb

input:

1 1 1
0 1
0 1

output:

1

result:

ok single line: '1'

Test #163:

score: 0
Accepted
time: 229ms
memory: 125060kb

input:

1 300000 2
1 1000000000
95793 95794
183348 183349
106929 106930
214389 214390
194596 194597
117176 117177
232220 232221
38012 38013
238156 238157
278704 278705
37706 37707
261566 261567
3035 3036
191271 191272
106836 106837
100612 100613
182274 182275
12445 12446
83006 83007
162601 162602
149279 149...

output:

300000

result:

ok single line: '300000'

Test #164:

score: 0
Accepted
time: 729ms
memory: 269824kb

input:

300000 300000 1666
210192556 210195888
430674328 430677660
14584164 14587496
830514328 830517660
129754744 129758076
780734248 780737580
31357452 31360784
17369716 17373048
158649848 158653180
903605080 903608412
398064044 398067376
993212556 993215888
635942188 635945520
130267872 130271204
7816172...

output:

600000

result:

ok single line: '600000'

Test #165:

score: 0
Accepted
time: 751ms
memory: 269468kb

input:

300000 300000 1666
962594808 962598140
982423540 982426872
932010380 932013712
574190232 574193564
416430028 416433360
868702380 868705712
405184528 405187860
71831256 71834588
278175352 278178684
906360644 906363976
828825004 828828336
816559912 816563244
734702668 734706000
586795188 586798520
554...

output:

600000

result:

ok single line: '600000'

Test #166:

score: 0
Accepted
time: 18ms
memory: 61280kb

input:

2000 2000 499500
293 294
859 860
545 546
112 113
587412000 588411000
235764000 236763000
416 417
441558000 442557000
888111000 889110000
359 360
748251000 749250000
932067000 933066000
559440000 560439000
621 622
223 224
733 734
285714000 286713000
917 918
403 404
195 196
711288000 712287000
4 5
109...

output:

4000

result:

ok single line: '4000'

Test #167:

score: 0
Accepted
time: 19ms
memory: 61304kb

input:

2000 2000 499500
177822000 178821000
895104000 896103000
610389000 611388000
938 939
214 215
88911000 89910000
719280000 720279000
63936000 64935000
699 700
992 993
142 143
92 93
825 826
995 996
899100000 900099000
872127000 873126000
849150000 850149000
77 78
717 718
493 494
783216000 784215000
664...

output:

3999

result:

ok single line: '3999'

Test #168:

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

input:

20000 20000 49995
3464 3465
3501 3502
7981 7982
1424 1425
621137880 621237870
3555 3556
6908 6909
483851610 483951600
715528440 715628430
4422 4423
3648 3649
2268 2269
677832210 677932200
1566 1567
357164280 357264270
288071190 288171180
494850510 494950500
435 436
9985 9986
4957 4958
7796 7797
1813...

output:

40000

result:

ok single line: '40000'

Test #169:

score: 0
Accepted
time: 34ms
memory: 69704kb

input:

20000 20000 49995
290070990 290170980
6405 6406
4922 4923
390760920 390860910
520647930 520747920
8146 8147
2125 2126
8037 8038
659234070 659334060
8704 8705
2571 2572
564843510 564943500
3552 3553
673932600 674032590
528447150 528547140
905509440 905609430
1070 1071
1396 1397
7160 7161
1667 1668
96...

output:

39999

result:

ok single line: '39999'

Test #170:

score: 0
Accepted
time: 725ms
memory: 269032kb

input:

300000 300000 1676
987224336 987227688
605863944 605867296
899438808 899442160
272866208 272869560
802093376 802096728
39318960 39322312
695218208 695221560
376295520 376298872
226055528 226058880
933350992 933354344
142094632 142097984
186344384 186347736
796267600 796270952
417005560 417008912
205...

output:

600000

result:

ok single line: '600000'

Test #171:

score: 0
Accepted
time: 770ms
memory: 268952kb

input:

300000 300000 1676
340764320 340767672
241447912 241451264
661674744 661678096
215174936 215178288
200526696 200530048
500775392 500778744
720887824 720891176
399260072 399263424
25756768 25760120
387303488 387306840
256669344 256672696
446281928 446285280
428295096 428298448
67170728 67174080
92727...

output:

599999

result:

ok single line: '599999'

Test #172:

score: 0
Accepted
time: 519ms
memory: 149688kb

input:

300000 300000 1
956392623 956392780
320175173 320175222
762107067 762107589
313931484 313931604
717975229 717979263
11194215 11194530
242937070 242937657
71574473 71574711
988529218 988531597
186803059 186803493
277161408 277161653
317277509 317278550
135253043 135253554
730675615 730676372
65021040...

output:

600000

result:

ok single line: '600000'

Test #173:

score: 0
Accepted
time: 15ms
memory: 60772kb

input:

2000 2000 1000000000
848124921 848228077
682809492 682811659
597385251 597577667
887967024 888259225
971021275 971037152
636971588 637468725
250251409 250579635
167261427 167525526
692026277 692112109
661664451 661669162
47861723 47863838
31873619 32231194
294548030 294950332
913530509 913951542
617...

output:

2000

result:

ok single line: '2000'

Test #174:

score: 0
Accepted
time: 400ms
memory: 138788kb

input:

300000 300000 1000000000
729508896 729509036
642114741 642115078
19752537 19754183
354692465 354692670
740192579 740195150
35823500 35826218
692915713 692916413
82249072 82250906
624765479 624765626
769436146 769436919
226588518 226590442
331625945 331626193
607209186 607210266
941057130 941060813
3...

output:

300000

result:

ok single line: '300000'

Test #175:

score: 0
Accepted
time: 23ms
memory: 60664kb

input:

2000 2000 1000000000
1934 1935
894 895
1805 1806
1335 1336
476 477
1037 1038
873 874
1727 1728
1246 1247
246 247
917 918
1844 1845
326 327
792 793
412 413
372 373
1603 1604
252 253
1220 1221
507 508
151 152
1674 1675
287 288
199 200
1474 1475
13 14
364 365
491 492
1781 1782
1173 1174
555 556
1441 14...

output:

2000

result:

ok single line: '2000'

Test #176:

score: 0
Accepted
time: 414ms
memory: 139332kb

input:

300000 300000 1000000000
257364 257365
253858 253859
281753 281754
29770 29771
17527 17528
228299 228300
105445 105446
236305 236306
50437 50438
24773 24774
71339 71340
269369 269370
268661 268662
281725 281726
92467 92468
13207 13208
271600 271601
44858 44859
12150 12151
244651 244652
206654 206655...

output:

300000

result:

ok single line: '300000'

Test #177:

score: 0
Accepted
time: 20ms
memory: 60716kb

input:

2000 2000 2000
1442 1443
98 99
1094 1095
850 851
255 256
659 660
1767 1768
1262 1263
1583 1584
623 624
452 453
1089 1090
880 881
1317 1318
1162 1163
1530 1531
286 287
482 483
1195 1196
1874 1875
910 911
1012 1013
242 243
1616 1617
1485 1486
1863 1864
1576 1577
145 146
812 813
398 399
367 368
16 17
1...

output:

2000

result:

ok single line: '2000'

Test #178:

score: 0
Accepted
time: 377ms
memory: 138416kb

input:

300000 300000 300000
106375 106376
247548 247549
177226 177227
119319 119320
19937 19938
129324 129325
261912 261913
99796 99797
134268 134269
234021 234022
208240 208241
28230 28231
30016 30017
126681 126682
183324 183325
90274 90275
20929 20930
55407 55408
163162 163163
164344 164345
230290 230291...

output:

300000

result:

ok single line: '300000'

Test #179:

score: 0
Accepted
time: 132ms
memory: 81052kb

input:

38926 105054 4
292027 292038
137838 137841
275249 275252
17166 17168
61447 61449
85952 85960
208056 208057
85250 85251
84029 84030
127120 127121
163293 163297
148212 148219
175404 175409
61553 61557
186496 186510
213215 213219
42579 42596
148771 148772
231122 231130
11096 11101
252150 252152
189099 ...

output:

113331

result:

ok single line: '113331'

Test #180:

score: 0
Accepted
time: 207ms
memory: 102644kb

input:

91231 177570 5
236630 236631
164330 164331
29785 29786
140336 140337
97870 97871
204785 204790
276552 276553
219316 219318
145416 145423
59864 59865
77647 77651
49384 49385
173987 173989
168418 168420
201760 201761
89505 89509
164088 164092
154175 154180
33882 33883
22672 22673
36399 36404
53068 530...

output:

178248

result:

ok single line: '178248'

Test #181:

score: 0
Accepted
time: 182ms
memory: 93828kb

input:

80849 131545 9
287908 287909
227064 227065
189711 189713
136765 136772
140276 140278
278389 278390
180653 180656
72806 72809
264318 264319
204442 204446
53660 53662
231836 231837
276251 276252
188297 188299
130128 130133
222572 222573
184412 184414
179380 179381
90037 90041
47114 47115
144066 144069...

output:

132132

result:

ok single line: '132132'

Test #182:

score: 0
Accepted
time: 520ms
memory: 151352kb

input:

300000 300000 4
423365414 423366872
392307425 392309841
686350343 686350616
26863337 26868019
953846670 953848875
428392014 428398089
302150831 302151333
235862368 235862482
86711859 86713564
580953589 580954257
895107735 895107900
556628754 556629664
612828576 612830005
741893904 741893910
52876246...

output:

600000

result:

ok single line: '600000'

Test #183:

score: 0
Accepted
time: 515ms
memory: 149380kb

input:

300000 300000 5
453478751 453479399
928102340 928103173
462373613 462373615
326474182 326474786
580480752 580480915
127148557 127148762
5028508 5031947
554104622 554105094
62840224 62840678
16354327 16355653
531703073 531706332
766512723 766514919
110213460 110213526
956656570 956656975
190962370 19...

output:

600000

result:

ok single line: '600000'

Test #184:

score: 0
Accepted
time: 474ms
memory: 149716kb

input:

300000 300000 9
694401084 694402345
956891602 956891638
723118008 723118639
751955008 751957667
892880712 892885464
275530904 275534468
414224982 414225193
566336585 566336656
531852869 531852897
698491726 698500435
363909937 363910132
985637501 985638839
938284292 938289352
133741794 133741797
4715...

output:

600000

result:

ok single line: '600000'

Test #185:

score: 0
Accepted
time: 291ms
memory: 128796kb

input:

67825 295842 53
252412 252416
162174 162175
26138 26140
292137 292138
256967 256968
101103 101121
213768 213769
10362 10364
235368 235370
131696 131697
245178 245179
32953 32954
249898 249900
53687 53688
237013 237015
296464 296466
170451 170452
239452 239458
21308 21312
247359 247361
158633 158634
...

output:

295791

result:

ok single line: '295791'

Test #186:

score: 0
Accepted
time: 171ms
memory: 95412kb

input:

32176 167088 40
278140 278144
218077 218078
182605 182607
123792 123793
150823 150828
55735 55737
103611 103612
78029 78033
25607 25610
69701 69704
7781 7795
100977 100978
244257 244260
208512 208522
165832 165834
199046 199047
186149 186152
223080 223083
175144 175147
251750 251755
82190 82191
1086...

output:

167068

result:

ok single line: '167068'

Test #187:

score: 0
Accepted
time: 184ms
memory: 98852kb

input:

142984 87556 27
80847 80848
29430 29431
224150 224151
135490 135491
263333 263334
10556 10560
255041 255042
256130 256133
179841 179844
114243 114246
106229 106230
187864 187868
297868 297869
10214 10215
174012 174013
106606 106607
275422 275423
266950 266951
255676 255677
71024 71026
114176 114179
...

output:

142984

result:

ok single line: '142984'

Test #188:

score: 0
Accepted
time: 485ms
memory: 150460kb

input:

300000 300000 53
409435688 409437909
295770411 295771254
72582164 72582471
972970218 972974130
47682433 47682826
969657568 969658274
925141414 925145166
69107184 69108097
186515056 186516121
842407796 842412907
95607965 95608525
962219142 962219574
961156292 961156389
213692029 213695128
662133760 6...

output:

599961

result:

ok single line: '599961'

Test #189:

score: 0
Accepted
time: 506ms
memory: 150892kb

input:

300000 300000 40
305630788 305630857
783369733 783369828
414766749 414766953
35322181 35326129
900372259 900372536
169429657 169434660
903459636 903461652
991266142 991268072
3924881 3925325
818143639 818145895
256476728 256478119
245481086 245481146
80765239 80765559
305907539 305912200
357297372 3...

output:

599988

result:

ok single line: '599988'

Test #190:

score: 0
Accepted
time: 493ms
memory: 151008kb

input:

300000 300000 27
637926546 637928407
601337788 601338680
238176547 238176725
60027691 60027966
454390231 454391020
156197638 156201294
619961672 619962779
440612348 440614158
472960927 472964216
915464080 915464185
112301806 112302163
861072697 861072706
435438292 435438699
334089362 334089478
74017...

output:

599996

result:

ok single line: '599996'

Test #191:

score: 0
Accepted
time: 224ms
memory: 109460kb

input:

223997 98541 3228
229793 229796
27884 27885
168542 168543
180276 180277
167302 167303
59557 59558
116343 116344
177525 177526
168222 168224
240986 240987
199039 199040
114519 114520
44998 44999
88624 88626
167287 167288
52023 52024
288562 288563
264763 264764
241266 241268
136686 136687
208223 20822...

output:

223997

result:

ok single line: '223997'

Test #192:

score: 0
Accepted
time: 228ms
memory: 103800kb

input:

35960 258898 2427
68515 68518
137543 137547
27213 27214
258605 258609
53633 53636
253028 253031
20286 20287
142872 142873
210605 210606
93174 93179
44309 44310
254670 254675
129395 129402
89837 89838
186196 186209
285283 285284
252385 252391
20940 20947
131321 131322
214090 214105
184394 184397
9213...

output:

256806

result:

ok single line: '256806'

Test #193:

score: 0
Accepted
time: 225ms
memory: 105232kb

input:

109548 184785 7613
234450 234451
123024 123026
95922 95923
85989 85991
46616 46617
32134 32136
128850 128853
141454 141455
84740 84741
229673 229674
17674 17676
151029 151032
57830 57831
241457 241458
76764 76765
76562 76564
10000 10001
69274 69275
166543 166544
63152 63154
123279 123280
250221 2502...

output:

180129

result:

ok single line: '180129'

Test #194:

score: 0
Accepted
time: 530ms
memory: 149776kb

input:

300000 300000 3228
261131071 261132779
856151450 856151745
471224772 471225025
11456191 11464296
400017333 400017474
904071351 904072629
335491967 335493043
921647695 921649009
346510197 346510223
472137219 472144901
224223794 224225363
638845970 638845972
370404506 370409284
495145020 495147384
680...

output:

443607

result:

ok single line: '443607'

Test #195:

score: 0
Accepted
time: 495ms
memory: 151824kb

input:

300000 300000 2427
974594054 974594543
88520602 88525826
244479656 244480410
675908581 675908655
577651442 577651450
194462527 194463545
146988850 146998065
924367305 924368191
63000950 63001172
551658555 551658820
670523879 670528460
318558577 318558786
172022559 172024578
151846381 151847687
48656...

output:

479549

result:

ok single line: '479549'

Test #196:

score: 0
Accepted
time: 491ms
memory: 151432kb

input:

300000 300000 7613
834341265 834348364
931158510 931159228
43898369 43899022
312563225 312568152
733420069 733422958
234356875 234357442
101566018 101568300
304897458 304897595
834533197 834533451
335188750 335190114
877350897 877351035
423617355 423617707
527241647 527242232
772046495 772047870
381...

output:

364094

result:

ok single line: '364094'

Test #197:

score: 0
Accepted
time: 235ms
memory: 126704kb

input:

297691 79313 151779
1874 1875
6963 6964
144115 144116
257791 257792
89564 89565
74056 74057
15109 15110
150664 150665
111963 111964
12688 12689
24350 24351
13515 13516
274795 274796
204501 204502
129689 129690
270780 270781
3763 3764
9922 9923
151128 151129
288410 288411
185071 185072
64952 64953
13...

output:

297691

result:

ok single line: '297691'

Test #198:

score: 0
Accepted
time: 136ms
memory: 84840kb

input:

92119 122459 212633
209081 209088
259875 259876
268335 268336
201494 201495
223147 223150
231170 231172
163315 163323
187784 187789
143741 143744
238937 238938
216733 216736
11762 11766
144554 144556
274671 274673
245214 245215
199417 199418
123102 123103
180254 180255
595 597
129804 129805
275710 2...

output:

92119

result:

ok single line: '92119'

Test #199:

score: 0
Accepted
time: 330ms
memory: 135180kb

input:

169955 273526 90198
247160 247161
114598 114599
283561 283562
170217 170219
284580 284581
96069 96071
104150 104151
131905 131906
140250 140251
279461 279462
190882 190883
139042 139043
94274 94275
265975 265976
54942 54943
156265 156266
131032 131033
250950 250952
44546 44547
214437 214438
287183 2...

output:

191351

result:

ok single line: '191351'

Test #200:

score: 0
Accepted
time: 499ms
memory: 150980kb

input:

300000 300000 151779
322779786 322779836
496405276 496406009
149199321 149201389
997875445 997875654
193967562 193968382
941960606 941961091
615891708 615894120
419683638 419683650
568445003 568445472
930278572 930286566
570269908 570269909
820845646 820846003
445686892 445686906
443271242 443272312...

output:

303178

result:

ok single line: '303178'

Test #201:

score: 0
Accepted
time: 527ms
memory: 149724kb

input:

300000 300000 212633
633548336 633549836
411187390 411188878
960047512 960048729
960431044 960433705
53279939 53281343
673189930 673192350
142408949 142409897
180535147 180536230
100713504 100714089
891300631 891301622
236682811 236682927
927840158 927840272
967055389 967056905
848209490 848209716
5...

output:

302398

result:

ok single line: '302398'

Test #202:

score: 0
Accepted
time: 515ms
memory: 150020kb

input:

300000 300000 90198
564636836 564637507
714693252 714693559
901713273 901713441
592172487 592174763
65303949 65307531
389109923 389110000
800925031 800925255
35804069 35804580
108125073 108125899
258180595 258180868
508065657 508066038
597922028 597922141
672161536 672161555
991422908 991423233
5612...

output:

305793

result:

ok single line: '305793'

Test #203:

score: 0
Accepted
time: 358ms
memory: 133836kb

input:

188336 266403 223134564
66660519 66686655
929722087 929728150
320533974 320535757
551818477 551819202
718131461 718132603
869670122 869674803
184204041 184206529
688358279 688364707
225801176 225803140
34367294 34367537
520050539 520064533
626007217 626013859
472102967 472110403
245251303 245252611
...

output:

207154

result:

ok single line: '207154'

Test #204:

score: 0
Accepted
time: 101ms
memory: 81516kb

input:

114772 59506 822684767
110230752 110235132
828142882 828142930
983760597 983767749
989706045 989708150
94050953 94051093
579992390 579992726
859169467 859169496
317901628 317902692
454644163 454655232
278005601 278005908
649619781 649626088
222988618 222990047
90622283 90624141
36170363 36170760
725...

output:

114772

result:

ok single line: '114772'

Test #205:

score: 0
Accepted
time: 457ms
memory: 145976kb

input:

300000 300000 459111407
45845236 45845470
39163785 39164332
106113469 106116668
269827582 269827633
210509226 210509277
487993531 487993724
90857304 90860014
907228660 907228892
917593089 917594055
161936902 161939469
643325792 643326167
463143815 463144350
863667004 863667732
120605625 120606322
97...

output:

300000

result:

ok single line: '300000'

Test #206:

score: 0
Accepted
time: 17ms
memory: 60400kb

input:

1 1 1000000000
573069483 659841614
124030676 970152998

output:

1

result:

ok single line: '1'

Test #207:

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

input:

1 1 157846707
315405347 347242626
272345064 321347240

output:

1

result:

ok single line: '1'

Test #208:

score: 0
Accepted
time: 12ms
memory: 60292kb

input:

1 1 950798221
848389079 854092696
557367377 764657729

output:

1

result:

ok single line: '1'

Test #209:

score: 0
Accepted
time: 27ms
memory: 60336kb

input:

1 1 671388450
985450784 997926763
398118617 456717283

output:

1

result:

ok single line: '1'

Test #210:

score: 0
Accepted
time: 13ms
memory: 60320kb

input:

1 1 364785590
787596086 902261955
4500940 696358894

output:

2

result:

ok single line: '2'

Test #211:

score: 0
Accepted
time: 20ms
memory: 60320kb

input:

2 2 731145322
322303121 980663386
152387287 265984398
369686386 731768078
791079349 819122146

output:

2

result:

ok single line: '2'

Test #212:

score: 0
Accepted
time: 15ms
memory: 62340kb

input:

2 2 118961482
762301953 837312354
938560516 978390380
804287014 865321213
111110615 421854728

output:

3

result:

ok single line: '3'

Test #213:

score: 0
Accepted
time: 24ms
memory: 60460kb

input:

2 2 866022286
711666220 790954560
36367669 268430929
385436503 388910161
522080374 656664464

output:

2

result:

ok single line: '2'

Test #214:

score: 0
Accepted
time: 12ms
memory: 60420kb

input:

2 2 579190821
653410060 992587848
535619927 539053192
111959224 117112685
117359938 566618757

output:

2

result:

ok single line: '2'

Test #215:

score: 0
Accepted
time: 519ms
memory: 151296kb

input:

300000 300000 1549
152474545 152490679
516945184 516945319
974712602 974713096
838548463 838550129
795373736 795377332
961114316 961114421
160038829 160048393
292024777 292027682
64259846 64261849
260655561 260655982
64254159 64257592
144437223 144440518
141523176 141523379
697397286 697404178
95675...

output:

532405

result:

ok single line: '532405'

Test #216:

score: 0
Accepted
time: 515ms
memory: 151296kb

input:

300000 300000 2131
750314739 750318066
459422437 459423408
457569370 457571978
983716184 983721495
437115258 437115333
232360836 232361056
798801253 798801683
590073215 590073946
264106462 264107344
408723067 408723419
349446666 349449685
888280455 888285146
108464485 108465793
681943370 681943474
5...

output:

496010

result:

ok single line: '496010'

Test #217:

score: 0
Accepted
time: 516ms
memory: 151316kb

input:

300000 300000 2847
724810421 724816810
397195825 397196449
199070434 199071830
314294563 314295008
27505431 27505753
452752915 452758542
377656915 377657997
634873285 634874986
266546508 266546835
634469695 634470750
967104012 967104274
156344730 156346081
755023744 755023793
687942293 687942831
239...

output:

459920

result:

ok single line: '459920'

Test #218:

score: 0
Accepted
time: 542ms
memory: 150212kb

input:

300000 300000 915
30032808 30033017
721401432 721401435
473888069 473890612
820608541 820610289
80085360 80085428
374538960 374541301
695092421 695092437
556647515 556649017
404036651 404047029
88918923 88918930
696711222 696711401
965271781 965271838
96158038 96158404
35999363 36000029
227542667 22...

output:

572392

result:

ok single line: '572392'

Test #219:

score: 0
Accepted
time: 520ms
memory: 151904kb

input:

300000 300000 1742
873872750 873873185
45058418 45058874
447588812 447590649
47245845 47247070
765321670 765323853
319070386 319071581
689375396 689378196
534075299 534077521
326684007 326684127
368312163 368316443
933529040 933530125
826158852 826158949
938868217 938868643
553882688 553888129
79107...

output:

519887

result:

ok single line: '519887'

Test #220:

score: 0
Accepted
time: 87ms
memory: 92692kb

input:

215315 2 5
229274 229275
34598 34599
45128 45129
21513 21514
241696 241698
171204 171205
56682 56683
52458 52459
228982 228983
62755 62756
297335 297336
81007 81008
9276 9278
263032 263034
82978 82979
28357 28358
242483 242484
256418 256419
47628 47629
186770 186771
216872 216873
148970 148971
98232...

output:

215315

result:

ok single line: '215315'

Test #221:

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

input:

214880 2 4
245667 245668
288276 288277
165379 165381
230317 230318
191582 191583
222136 222137
231750 231751
209724 209725
177002 177003
79875 79876
155494 155496
51739 51740
53342 53343
264589 264590
268532 268533
16133 16134
295053 295054
24033 24034
28447 28448
148716 148718
40871 40872
191204 19...

output:

214882

result:

ok single line: '214882'

Test #222:

score: 0
Accepted
time: 132ms
memory: 97868kb

input:

2 258235 5
223565 282522
293045 296861
228457 228458
283573 283574
257493 257494
165882 165883
248544 248546
216783 216784
52368 52369
230356 230357
180859 180860
102231 102232
122896 122897
261798 261799
218223 218224
204321 204322
72779 72780
280413 280414
290754 290755
91994 91995
36242 36243
253...

output:

258230

result:

ok single line: '258230'

Test #223:

score: 0
Accepted
time: 123ms
memory: 93596kb

input:

2 210807 9
164407 164942
165401 225514
56976 56977
155019 155020
41550 41551
197568 197569
164655 164656
197569 197570
180088 180089
170763 170764
285777 285778
119059 119060
108074 108075
129316 129317
111220 111221
25077 25078
96788 96789
57570 57571
282805 282806
208217 208218
1552 1553
254559 25...

output:

210801

result:

ok single line: '210801'

Test #224:

score: 0
Accepted
time: 165ms
memory: 118772kb

input:

300000 1 86
625435260 625435432
173678497 173678643
720963764 720964177
174408893 174409039
267054798 267055363
763308227 763316523
566389441 566390242
625058017 625058922
970314161 970315558
108485271 108486370
234631012 234632761
272003679 272003743
150779764 150781754
768323325 768324675
89282699...

output:

300001

result:

ok single line: '300001'

Test #225:

score: 0
Accepted
time: 154ms
memory: 116832kb

input:

300000 1 247
784145676 784147129
274009638 274017318
626001137 626002134
211683764 211687190
976918954 976919006
131102289 131102570
468046925 468046932
46600129 46612473
636631228 636631281
636180984 636190108
330660861 330664200
282857074 282860675
803486193 803486789
643276698 643278192
802219606...

output:

300001

result:

ok single line: '300001'

Test #226:

score: 0
Accepted
time: 167ms
memory: 116500kb

input:

1 300000 216
309539592 491468242
797539695 797540953
339929370 339929396
675848577 675849274
10158839 10159146
60354473 60354533
524693899 524694457
685231035 685231076
764240587 764243489
362479842 362482099
640431249 640431272
265981545 265984790
325276337 325277604
378615528 378615945
284115659 2...

output:

300001

result:

ok single line: '300001'

Test #227:

score: 0
Accepted
time: 149ms
memory: 116360kb

input:

1 300000 172
276384969 302138380
892082256 892082470
893318193 893319966
656812474 656813525
15294691 15296210
244739340 244739347
365343730 365343788
948845624 948846035
244320731 244321472
158957678 158958063
867716373 867720650
272377661 272378396
767252907 767254973
19637986 19645596
992918935 9...

output:

300001

result:

ok single line: '300001'

Test #228:

score: 0
Accepted
time: 189ms
memory: 121256kb

input:

300000 2 86
514296700 514300785
123961092 123961677
179650854 179653853
146791074 146791563
46287439 46287949
563806045 563806743
313093184 313100154
283567097 283567104
773659320 773659369
969729641 969729979
341061202 341061464
209103925 209111332
752894207 752894272
212196164 212197957
298733809 ...

output:

300002

result:

ok single line: '300002'

Test #229:

score: 0
Accepted
time: 193ms
memory: 124648kb

input:

300000 2 247
163789556 163789646
59366862 59366994
590918578 590920583
340287883 340288307
832940568 832941862
583220550 583225806
795796713 795796763
696583653 696592660
865483461 865483473
807263763 807268659
242093220 242098835
136399195 136408676
305717620 305721696
606475268 606479044
642768249...

output:

300002

result:

ok single line: '300002'

Test #230:

score: 0
Accepted
time: 212ms
memory: 121764kb

input:

2 300000 216
996984492 998164917
131242902 728795061
642527594 642530361
301356283 301356916
790331224 790331260
369543590 369543621
296848744 296849060
805312794 805312848
130701735 130705488
214419220 214419633
903471292 903471405
856148372 856149436
789578008 789578114
32010128 32010867
677261445...

output:

300002

result:

ok single line: '300002'

Test #231:

score: 0
Accepted
time: 221ms
memory: 119736kb

input:

2 300000 172
891396571 966352676
393055575 798778789
519210800 519211001
417066945 417067525
948359238 948359394
455286799 455286856
745091323 745092545
168519510 168521482
563960455 563962133
767328941 767330092
523165301 523167511
679401121 679401856
614698754 614698890
630338565 630338791
8413558...

output:

300002

result:

ok single line: '300002'

Extra Test:

score: 0
Extra Test Passed