QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423977#8649. Escape Route 2flying100 ✓559ms43884kbC++142.7kb2024-05-28 20:22:292024-05-28 20:22:31

Judging History

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

  • [2024-05-28 20:22:31]
  • 评测
  • 测评结果:100
  • 用时:559ms
  • 内存:43884kb
  • [2024-05-28 20:22:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
const int B=500;

#define l first
#define r second

struct node
{
	int l,r;
};

node a[N];
vector <pair <int,int> > seg[N], que[N];
vector <int> id[N], key[N];
int to[N][20],cost[N][20],L[N*3],R[N*3],pos[N],val[N];
long long ans[N*3];

bool cmp(node a,node b)
{
	if(a.r!=b.r)
		return a.r<b.r;
	return a.l>b.l;
}

int main()
{
	int n,T;
	cin >> n >> T;
	for(int i=1;i<n;i++)
	{
		int k;
		scanf("%d",&k);
		for(int i=1;i<=k;i++)
			scanf("%d %d",&a[i].l,&a[i].r);

		sort(a+1,a+k+1,cmp);

		int maxl=-1, cnt=0;
		for(int i=1;i<=k;i++)
			if(a[i].l>maxl)
				maxl=a[i].l, a[++cnt]=a[i];
		k=cnt;

		for(int j=1;j<=k;j++)
			seg[i].push_back(make_pair(a[j].l,a[j].r));
	}

	int indx=0;
	for(int i=1;i<n;i++)
		for(int j=0;j<seg[i].size();j++)
			id[i].push_back(++indx);

	for(int i=1;i<n-1;i++)
	{
		for(int j=0;j<seg[i].size();j++)
			if(seg[i][j].r<=seg[i+1].back().l)
			{
				to[id[i][j]][0]=id[i+1][lower_bound(seg[i+1].begin(),seg[i+1].end(),make_pair(seg[i][j].r,0))-seg[i+1].begin()];
				cost[id[i][j]][0]=0;
			}
			else
			{

				to[id[i][j]][0]=id[i+1][0];
				cost[id[i][j]][0]=1;
			}
	}

	for(int j=1;j<20;j++)
		for(int i=1;i+(1<<j)-1<=indx;i++)
		{
			to[i][j]=to[to[i][j-1]][j-1];
			cost[i][j]=cost[i][j-1]+cost[to[i][j-1]][j-1];
		}

	int q;
	cin >> q;
	for(int i=1;i<=q;i++)
	{
		scanf("%d %d",&L[i],&R[i]);
		R[i]--;
		if(R[i]-L[i]<=B)
			que[L[i]].push_back(make_pair(R[i],i));
	}

	for(int i=1;i<=n;i++)
		sort(que[i].begin(),que[i].end());

	for(int i=1;i<n;i++)
	{
		int sz=seg[i].size();
		for(int k=0;k<sz;k++)
			pos[k]=id[i][k], val[k]=0;

		int now=0;
		for(int j=i;j<=i+B;j++)
		{
			long long nowans=1e18;
			for(int k=0;k<sz;k++)
				nowans=min(nowans,1ll*val[k]*T+seg[j][pos[k]-id[j][0]].r-seg[i][k].l);

			while(now<que[i].size() && que[i][now].first==j)
			{
				ans[que[i][now].second]=nowans;
				now++;
			}

			if(j==n-1)
				break;

			for(int k=0;k<sz;k++)
				val[k] += cost[pos[k]][0], pos[k]=to[pos[k]][0];
		}

		pos[sz]=-1;
		for(int k=0;k<sz;k++)
			if(pos[k]!=pos[k+1] || val[k]!=val[k+1])
				key[i].push_back(k);
	}

	for(int i=1;i<=q;i++)
		if(!ans[i])
		{
			int l=L[i], r=R[i];
			long long ans=1e18;
			for(int t=0;t<key[l].size();t++)
			{
				int j=key[l][t], need=r-l, val=0, pos=id[l][j];
				for(int i=16;i>=0;i--)
					if((need>>i)&1)
					{
						val += cost[pos][i];
						pos = to[pos][i];
					}

				ans=min(ans,seg[r][pos-id[r][0]].r-seg[l][j].l+1ll*T*val);
			}
			printf("%lld\n",ans);
		}
		else
			printf("%lld\n",ans[i]);
	return 0;
}

詳細信息

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 37ms
memory: 24732kb

input:

2 1000000000
1
359893566 955414858
300000
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 ...

output:

595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
...

result:

ok 300000 lines

Test #2:

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

input:

1384 702597566
1
93593482 288383752
1
483624997 516514674
1
217174776 378882844
1
381889032 694179867
1
143192510 343368096
1
20552425 654877612
1
34995000 223673833
1
86047336 507288111
1
58193455 564074888
1
543118270 579455813
1
42236607 257802041
1
244371899 634806939
1
173261583 634917538
1
245...

output:

152061320763
364193581975
101659406868
515885206553
273965799122
114948644944
78108129814
549857539900
166576516139
266640269522
36194858709
249707922175
12419530470
164111155048
607789899481
370597406072
100093371327
351888389540
72528927782
102643452509
26254171517
335577444460
126061743618
214062...

result:

ok 235294 lines

Test #3:

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

input:

2000 1000000000
1
251243678 591560449
1
994358883 999558886
1
322667352 514836853
1
538977337 603533309
1
249401760 363153703
1
104249966 416969473
1
103160611 933539967
1
300026318 706474995
1
637853185 969624295
1
612852422 686323121
1
890842468 964096005
1
127364216 656085651
1
565856726 79766828...

output:

804591361552
615732551026
616673957607
255388778080
246824759617
250452018635
3920166700
411598001493
191141891280
437294118321
839203030077
237616086785
395724762439
24493946848
261496520138
440921377339
879523097721
632991245786
629587780307
208737211703
514022647807
1235201434706
1239644739996
51...

result:

ok 300000 lines

Test #4:

score: 0
Accepted
time: 49ms
memory: 25592kb

input:

2000 702597566
1
234199188 250686543
1
187177414 485066634
1
187177414 584601655
1
187177414 584601655
1
472618361 588604455
1
619085294 688959957
1
619085294 661784753
1
218487968 619085294
1
619085294 642882128
1
260718505 642882128
1
599405824 642882128
1
609069701 699150927
1
609069701 702336507...

output:

1015957000190
680210081647
1242056863771
237697116977
4956604203
134440244240
408395990203
826647972707
545108473847
444013368984
460270771687
398420505294
739873557581
11886903864
782516902871
622468211441
160076268243
501156545599
68094738139
94221928973
846316719734
79740931643
53785803546
225843...

result:

ok 235294 lines

Test #5:

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

input:

2000 1000000000
1
68118109 979507132
1
314757325 876264736
1
314757325 876264736
1
67889892 777031974
1
482602023 935398234
1
262404428 482602023
1
339427172 407785939
1
387917774 407785939
1
326338674 387917774
1
470606759 626121253
1
479458047 617726881
1
497240208 588812091
1
27983270 580400619
1...

output:

1058954050793
1702912646711
1725931854894
847704535346
735930701349
957982043978
689218108574
1014888485270
1253926159509
5082345003
326705049247
551722648510
670690834144
772997962207
64935508636
584174883094
608974709405
109201814393
118555421706
191964764942
1461647551481
1384656185989
3160951073...

result:

ok 300000 lines

Test #6:

score: 0
Accepted
time: 68ms
memory: 24024kb

input:

2000 1000000000
1
0 318307689
1
221844870 244163115
1
22662231 115199498
1
74219194 235801812
1
2902409 380433342
1
168375604 683138088
1
11701354 403914303
1
168632344 336967772
1
71867910 459961453
1
152644723 678746968
1
600952102 753759227
1
623175732 906107261
1
630957186 647533253
1
283639625 ...

output:

1501632404753
1875961436118
1998999999999
230648011712
554515884946
1810332112158
1414199310905
464373332232
756701388718
1232357794991
594169425622
207539360194
1483145438544
601736569489
71450010792
12219064269
262122526111
724970057025
409281412575
949114178961
415313478501
59936197914
1681006375...

result:

ok 300000 lines

Test #7:

score: 0
Accepted
time: 54ms
memory: 23972kb

input:

1384 702597566
1
91563503 395118179
1
272969378 336163563
1
93593482 288383752
1
641844047 657030228
1
24174550 474302755
1
483624997 516514674
1
223419444 649396752
1
277453784 660782113
1
217174776 378882844
1
315641289 693735319
1
251526833 482373541
1
381889032 694179867
1
103075862 361871540
1
...

output:

320794118590
115764966304
385279850930
10774072710
147778102717
240803564048
431539589908
290543953614
569466251816
22113396174
135588695866
228196386401
212848381901
88271083633
28719105225
481452322932
162201684606
579266864
322128177133
432606465712
97136428753
117887869786
563426915735
106522969...

result:

ok 235294 lines

Test #8:

score: 0
Accepted
time: 67ms
memory: 24208kb

input:

2000 1000000000
1
351194706 960606958
1
63449901 293827916
1
251243678 591560449
1
130608720 233558964
1
711982590 994358883
1
64238880 999558886
1
373830184 840719930
1
450224484 514836853
1
322667352 903701287
1
258721955 861235059
1
229925996 538977337
1
546018536 603533309
1
656999554 814169249
...

output:

917540572198
186307563686
364348161985
671810713222
368143529864
751354141909
398419559458
596576418307
19619304924
8364848267
507434978682
500879172382
200335632587
667972088008
955278113757
1106615668453
1200860863382
717853707983
277931060293
664485590193
152444963228
296133779011
563469393776
33...

result:

ok 300000 lines

Subtask #2:

score: 8
Accepted

Dependency #1:

100%
Accepted

Test #9:

score: 8
Accepted
time: 60ms
memory: 27372kb

input:

401 1000000000
5
220371372 336231535
896142843 932588962
50422118 103225530
657147900 709375447
431588410 552424272
5
640842473 746383340
810978611 953826580
275021460 368433859
462990882 571587967
58700188 103678512
5
671571439 779339183
471320804 598246091
2249112 160803576
865566830 948052278
222...

output:

58015892805
52459605973
79838077191
17461955998
14664444928
41031111167
44824194366
23803651939
61071315346
12828269099
37025588232
22632816685
3687297996
23869715688
53256120071
26611104179
27660022154
43657337431
43421554887
33052332827
444354092
2245599618
3207243655
52828823244
29244408625
18672...

result:

ok 300000 lines

Test #10:

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

input:

401 1000000000
5
530204134 539929589
13144227 22318244
346386878 374628522
243477806 318307686
24550570 176767937
5
318307686 346386878
539929589 592275682
176767937 243477806
22318244 24550570
374628522 530204134
5
24550570 176767937
243477806 318307686
13144227 22318244
530204134 539929589
3463868...

output:

37011406343
19273967996
39579131455
169618941
18197860585
17273967996
13296451783
27169618941
3415507745
1333242651
26169618941
23517611345
8273967996
21517611345
1009174017
12526785362
27131150716
10333242651
20230333579
14056320836
22011406343
17296451783
3131150716
18011406343
20517611345
4352310...

result:

ok 300000 lines

Test #11:

score: 0
Accepted
time: 59ms
memory: 27400kb

input:

401 1000000000
4
848784509 854990717
82539068 388749940
876647585 917845619
434252359 592889838
5
917845619 963887179
388749940 434252359
854990717 876647585
592889838 848784509
79661360 82539068
4
434252359 592889838
876647585 917845619
82539068 388749940
848784509 854990717
5
79661360 82539068
854...

output:

39069061110
33115102670
49881348111
37483593260
28483593260
20529095679
9838184259
28108896462
16575137239
27529095679
6838184259
40027863076
11108896462
30062854902
23881348111
15370997341
27069061110
11529634820
13370997341
4069061110
38115102670
28575137239
16006206208
324955781
10529095679
23115...

result:

ok 300000 lines

Test #12:

score: 0
Accepted
time: 61ms
memory: 25632kb

input:

401 1000000000
4
494963273 820408129
83880819 120938110
842771080 916665396
126044810 290806569
5
64152734 83880819
820408129 842771080
290806569 494963273
120938110 126044810
916665396 991266558
4
126044810 290806569
83880819 120938110
842771080 916665396
494963273 820408129
5
820408129 842771080
6...

output:

44795843296
23631081537
49907385739
29907385739
32283273730
2448035489
23056785376
14674555144
35056785376
3206925750
22206925750
11674555144
6448035489
13470398440
2061892076
13448035489
26061892076
674555144
1037057291
19907385739
5206925750
8631081537
2283273730
631081537
15470398440
42795843296
...

result:

ok 300000 lines

Test #13:

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

input:

601 1000000000
1
1875338 891632702
5
25665841 55060068
659511452 708955140
481273243 580847341
711209775 812323888
232189221 411128242
1
1875338 891632702
5
481273243 580847341
711209775 812323888
25665841 55060068
659511452 708955140
232189221 411128242
1
1875338 891632702
5
232189221 411128242
711...

output:

132889757364
545053184730
599053184730
349053184730
367180422927
378889757364
181053184730
214889757364
25053184730
119343850293
51180422927
165180422927
293180422927
367180422927
569343850293
449343850293
445053184730
115180422927
341053184730
218889757364
189053184730
107180422927
105343850293
272...

result:

ok 300000 lines

Test #14:

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

input:

2 1000000000
5
562116384 862271817
248809078 388152605
82837362 988267899
133736084 529736108
468265107 868556204
300000
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2...

output:

139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
...

result:

ok 300000 lines

Test #15:

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

input:

1343 1000000000
1
96816138 421462953
1
69729216 475015093
1
283255283 678004962
1
278183246 599578883
1
286424703 774388986
1
406934648 652124894
2
248195189 472085327
391961014 813907536
1
501741026 753654366
2
245060443 436672588
574556343 749900723
2
68441219 101302096
259996265 760303051
1
72484...

output:

413507395543
186533587467
765911134712
208868482018
750404829806
371009807668
207418964932
82428131468
227003029730
376762196348
758844081281
297910927314
116614837962
284886215974
115872729613
739953553340
22687331071
38063290673
8397417592
12376556003
111406561501
687952964749
12358874327
12241911...

result:

ok 300000 lines

Test #16:

score: 0
Accepted
time: 66ms
memory: 27276kb

input:

688 1000000000
3
53194187 264960020
92885755 475277088
211238915 509880505
3
6401156 232019227
469999920 577170462
554975681 644492768
2
60786527 521736047
379366223 840946783
5
419561 60298271
65502307 288235251
144008397 577008215
394990239 683091070
590837826 726885528
5
34176214 267349290
223828...

output:

68635449756
17399644966
829516162
145106947024
213624911279
172079871542
83795296584
86980633523
92389124653
242968110321
130973680158
126653516847
55386113669
195171481102
213220346364
18461195442
46294965858
108144706452
39788445054
253134167975
234247708477
234680737798
241401743091
222796922152
...

result:

ok 300000 lines

Test #17:

score: 0
Accepted
time: 61ms
memory: 24604kb

input:

1343 1000000000
1
109453710 560177810
1
661213206 913808522
1
96816138 421462953
1
193580993 240625496
1
418456250 930846898
1
69729216 475015093
2
36690281 582664217
176453344 242348112
1
283255283 678004962
2
62188679 608199380
90371766 461894091
2
278183246 599578883
255503843 861802590
1
5501148...

output:

755163082049
346535864122
512232407863
978898058885
290552425232
97892014092
196290407373
506354231170
334498014469
284757164242
115371682131
62648300672
346925420676
384891531485
477119667452
63592230021
727135372228
847646760248
640469173746
892644815785
815536555442
725960919828
92996821933
41864...

result:

ok 300000 lines

Test #18:

score: 0
Accepted
time: 61ms
memory: 25540kb

input:

688 1000000000
3
423977827 524383260
470022669 702490366
226130327 278353378
3
297592874 610688336
79889464 986165439
132108640 133164848
2
92885755 509880505
53194187 211238915
5
264960020 475277088
262659468 993117970
127768091 586472847
838692371 844797839
414832478 764033423
5
132569548 29971860...

output:

326730918498
121718776974
78578695164
28500146125
259901663572
262316540686
278578980688
83091064134
24828685743
280173281064
305172418316
69583809374
329513749863
295544205317
40964341057
32266429473
20655624467
142566212889
70252960623
218573155987
10170931375
250505042674
221374816018
41528906065...

result:

ok 300000 lines

Subtask #3:

score: 17
Accepted

Dependency #1:

100%
Accepted

Test #19:

score: 17
Accepted
time: 379ms
memory: 41460kb

input:

78947 750547470
1
163829932 170313421
1
34754818 519560348
1
93869768 456876196
1
202438570 204178463
1
98944286 525531897
1
179303298 240997860
1
134306886 372058731
1
187793519 715404428
1
126696643 473999960
1
394050514 679516860
1
286238164 460635018
1
489600305 744982147
1
157363526 311748138
1...

output:

6205466879608
20259844164215
41141586068816
37267587927279
39826818642517
4093515572405
43823341232727
17711628858751
28238993418477
40884190272133
26104208475807
13508775709102
41012054001186
35352426273830
461627182416
19671175078208
21652186528249
28225447363916
41145479364020
41071413078809
3081...

result:

ok 206901 lines

Test #20:

score: 0
Accepted
time: 507ms
memory: 43644kb

input:

100000 1000000000
1
499402020 514605324
1
766295491 995958303
1
96603365 780877499
1
712910081 985226165
1
454949900 743899539
1
21691952 722721408
1
211340490 405034439
1
85107353 123109353
1
706000294 838706369
1
38501709 366714034
1
197050586 597553366
1
394077551 422415760
1
722716322 890440304
...

output:

51002827556551
51058928322620
54456195364152
33985756298880
40843294364814
15102513736222
54474740890294
38132310544449
45962379244811
81828173456918
45953634597664
54383361960561
81724265807653
54486863608036
7943440845221
52922599405365
54528389564372
54359675413858
54480599618780
55927751535912
1...

result:

ok 300000 lines

Test #21:

score: 0
Accepted
time: 524ms
memory: 43396kb

input:

100000 1000000000
1
172079429 475324295
1
400518916 720769657
1
274370833 437066961
1
69640537 354880456
1
105708389 515119134
1
460245448 491168511
1
305736062 908867012
1
409879705 700345897
1
807448587 900734950
1
21167124 802349010
1
29646241 451672345
1
401101164 849231397
1
143742860 355220627...

output:

3322786217605
54519197542433
51507236182424
51038288475992
54515310283834
54451772579395
40445305754310
12499014691181
64287958279392
5165502765728
54536981294065
33993047573307
50203125083627
4287962267265
32543278978791
29553771479908
6634090289361
24497834416407
54510411009409
54478989372687
5448...

result:

ok 300000 lines

Test #22:

score: 0
Accepted
time: 455ms
memory: 43856kb

input:

100000 848784505
1
27033502 308637216
1
1438562 377905811
1
377905811 445448307
1
377905811 445448307
1
160564479 367847022
1
29086295 441763868
1
10492385 29086295
1
29086295 730214588
1
272693597 730214588
1
8185380 43275068
1
6374476 782898366
1
4005270 6374476
1
3501828 5751498
1
890858 5072034
...

output:

40155094458849
53957285623801
74314870396875
39710068492963
247825537284
9491774378246
1792570550982
11487043081182
39927445813086
7518209178048
1868430585731
9399975086886
42289338923347
7444371932154
16049020333361
46632817179506
40333365472902
22933944313580
38418501333554
23288694741242
47056670...

result:

ok 226053 lines

Test #23:

score: 0
Accepted
time: 559ms
memory: 43728kb

input:

100000 1000000000
1
83880822 730819402
1
35594124 752445375
1
18704793 668403352
1
17474165 931488188
1
15086956 950700936
1
35712962 969944984
1
969944984 988879345
1
978906485 997699198
1
988078833 989460959
1
333539740 989236085
1
992834981 993928865
1
993836625 993928865
1
993877892 993928865
1
...

output:

50616175045053
69001077953362
87602914201257
9400991126552
13076249428282
3302796985315
20277989521385
22218930829541
30336682428616
49125555454337
31148275992440
17955973903932
28958997325743
47631793498371
42949340374080
15065991559529
48988320931729
42577974657383
21914787769912
54987999529326
82...

result:

ok 300000 lines

Test #24:

score: 0
Accepted
time: 535ms
memory: 43680kb

input:

100000 1000000000
1
0 55060072
1
3570003 718349783
1
256078893 403790490
1
389580948 656859885
1
610267686 893795343
1
659511452 663711653
1
1875338 798640433
1
761217675 830966093
1
325102503 422332552
1
52703351 777206866
1
632813519 799618334
1
591942509 965790256
1
943567255 992355350
1
81550764...

output:

59312736241277
82196943632763
99998999999999
23986078307126
2509122248637
42012837406787
28611768219019
65210377806133
556560473013
15606679568159
5810556495394
46933725843182
71288948739119
11091807824559
90582129788769
23140905870202
17705197665416
25352553201248
38685906120426
55367891999341
9724...

result:

ok 300000 lines

Test #25:

score: 0
Accepted
time: 401ms
memory: 41812kb

input:

78947 750547470
1
12801326 300178508
1
163829932 629108909
1
170313421 475428191
1
419182442 552951314
1
34754818 519560348
1
3594075 419329694
1
456876196 654341696
1
29308134 93869768
1
83056966 497182026
1
204178463 450250065
1
202438570 465078541
1
55014422 368356153
1
98944286 386133586
1
52553...

output:

33684588782336
10599029692975
46269013081090
38276748912791
37664428117700
3243264461448
16441523547215
15541405847231
19207973709712
10394890624052
183262146076
14345085397720
28902769238369
3218092520743
33009007885846
10621151273560
29740815235729
48877373310335
36045937597311
10838456331639
2082...

result:

ok 206901 lines

Test #26:

score: 0
Accepted
time: 526ms
memory: 43884kb

input:

100000 1000000000
1
395765 716053221
1
208668935 499402020
1
514605324 573424149
1
112563488 430804151
1
766295491 995958303
1
370896512 442618404
1
155109978 225449821
1
96603365 780877499
1
305211230 986836650
1
322663385 970957503
1
712910081 985226165
1
297230409 621959309
1
208656221 743899539
...

output:

30662391785500
57766779240503
6111126043334
42002498505076
19753415630398
16369656055632
3834523157128
4728497583038
9546264570412
67330624722110
25516282773156
32679967205145
41165867776209
35357315307254
49979790494981
49838551462323
20813782279079
45227041005079
6586079790185
75982320601677
16933...

result:

ok 300000 lines

Subtask #4:

score: 23
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #27:

score: 23
Accepted
time: 325ms
memory: 38040kb

input:

20001 1000000000
5
662762967 798994894
46468971 138354131
892564074 912204331
409200282 595445952
230044234 398729067
5
57118027 151959518
229157851 303631723
814367320 981450020
659838968 768234790
439004698 573433651
5
630869543 717178196
17036982 173768392
493203667 591467829
827391797 966144141
...

output:

2668629630832
3892831280463
3999809623740
1226857097475
1113419685285
3489433065118
2368257576772
158657663807
3450834844047
68629258911
462031612601
914686104073
305462834488
526483864084
1947466042958
497468869738
948471959358
606415771236
1138412760182
1864844276046
1528229688813
710645087145
170...

result:

ok 300000 lines

Test #28:

score: 0
Accepted
time: 328ms
memory: 38112kb

input:

20001 1000000000
5
308621522 415553181
544387950 686788436
2910518 107270602
155048696 307278598
830887408 940209105
5
107270602 155048696
686788436 830887408
940209105 961624633
307278598 308621522
415553181 544387950
5
544387950 686788436
308621522 415553181
155048696 307278598
830887408 940209105...

output:

1713305711004
1320847770098
1999958714115
396260504485
443713500542
785308282579
162728764745
505713500542
928475344076
39001342924
1092412642663
228001342924
359855901028
109477734114
111477734114
716001342924
121713500542
223855901028
1287201350920
409728764745
223368412417
1371728764745
387604178...

result:

ok 300000 lines

Test #29:

score: 0
Accepted
time: 294ms
memory: 37488kb

input:

20001 1000000000
4
376385568 496774928
78267375 138949467
841454996 880233443
222277480 321404104
5
880233443 983583259
13092102 78267375
496774928 841454996
321404104 376385568
138949467 222277480
4
376385568 496774928
222277480 321404104
841454996 880233443
78267375 138949467
5
138949467 222277480...

output:

2117655319932
702209185378
2499905315884
508298118193
101905315884
1273298118193
604418507553
1189534930572
103534930572
565483682826
793209185378
1248905315884
15655319932
109142128263
1241418507553
261483682826
1705363293466
25363293466
688483682826
512534930572
1125655319932
375905315884
14730831...

result:

ok 300000 lines

Test #30:

score: 0
Accepted
time: 308ms
memory: 37412kb

input:

20001 1000000000
4
315185538 333342024
521319743 622886125
759132144 761216576
226575653 275596002
5
275596002 315185538
761216576 831323224
622886125 759132144
25143503 226575653
333342024 521319743
4
759132144 761216576
521319743 622886125
226575653 275596002
315185538 333342024
5
761216576 831323...

output:

1587294744090
1086555727222
2499604747571
300396310472
8806179721
286396310472
151057746022
26208437099
1805604747571
1865057746022
55534640923
698604747571
691534640923
1827604747571
1867396310472
816396310472
1881604747571
454736073073
1135308198521
855396310472
2172057746022
1157483536142
1031806...

result:

ok 300000 lines

Test #31:

score: 0
Accepted
time: 286ms
memory: 38292kb

input:

30001 1000000000
1
21117989 982275318
5
348955718 354892948
517766696 625348205
805456123 912649069
914857809 952207119
688887994 728026354
1
21117989 982275318
5
348955718 354892948
805456123 912649069
688887994 728026354
914857809 952207119
517766696 625348205
1
21117989 982275318
5
805456123 9126...

output:

17908961157329
20921333774959
29999333774959
25220961157329
11605067417509
12619067417509
7677333774959
1152961157329
3459333774959
3935067417509
10587440035139
28299440035139
2107440035139
23369440035139
2996961157329
8014961157329
13973067417509
13674961157329
22699333774959
3478961157329
16398961...

result:

ok 300000 lines

Test #32:

score: 0
Accepted
time: 340ms
memory: 39208kb

input:

52296 881005949
2
12638378 314608048
230277712 646023135
2
7970120 144826095
232289682 464453079
2
43074268 690542826
457137449 814350394
2
90590387 210651165
430322805 438108763
2
262122767 731114802
703888005 870307617
1
315512805 456058339
1
37476738 436885484
2
254218216 499413611
438320946 5376...

output:

15455798760730
11984607222285
20680790415602
4750544906379
3020336963331
20443131922032
23134339955552
16962146492370
9155044660439
31308651624859
20722406772139
8415826437128
14123486717595
20815714989210
20842841161072
10437622322545
17460173634323
18749758588676
18234945122566
15524384582174
1917...

result:

ok 225128 lines

Test #33:

score: 0
Accepted
time: 410ms
memory: 40464kb

input:

66656 1000000000
2
15637406 81199431
614401094 952427931
1
463757280 674231068
2
74142863 129147484
316487270 912769840
1
17077634 368244435
2
114585085 442617353
181318881 832328914
2
111870948 647897797
719462562 834163614
2
25819681 74547077
446917913 483756021
1
270282038 826567403
1
340447312 4...

output:

48099478257116
47513195224330
23132550086977
47440191378164
3259577300506
561076182783
35548782601046
47502699906957
47474804760637
25711248466185
47484643705582
761261858032
275189245596
23550672178341
45874628703220
41426247507288
10013250069301
47323222838401
40013531733954
45892625726417
4741594...

result:

ok 300000 lines

Test #34:

score: 0
Accepted
time: 249ms
memory: 36912kb

input:

22440 830108249
5
275540307 309024263
293591232 477947492
384611234 526667338
468270758 685508016
481560260 739708290
1
202061534 417627726
5
290757 18035972
38071595 99984307
162896273 445740814
189936111 476554990
195650129 497757952
2
6884658 472660927
219393347 557164578
2
169625177 613750054
36...

output:

7319209215260
6265873378031
5236894680967
5394283214691
6293940268386
3665363372040
7289438294194
7090839460098
7319712036853
3600006037646
7321019523257
7326482635715
6381021534848
8565532582826
3131065041122
3205302275744
3645505484457
355149148778
7328244396740
7291192261702
5064400938155
6860494...

result:

ok 291972 lines

Test #35:

score: 0
Accepted
time: 311ms
memory: 39136kb

input:

49512 982085869
2
191978970 744443612
363217661 667062768
1
180359100 880407268
2
259041363 304296352
284840288 673227746
1
28431521 368506138
1
565787827 607988959
2
606506192 942820159
537798608 786378991
2
15560056 480518061
289026559 655058004
2
33072594 226290400
327422566 902685917
2
796547625...

output:

2308597162767
5946652814798
12734126402298
33542731334092
22691855203909
15460214509232
67921277450
3769355551079
9269134832918
2066700010416
23221321710275
1790280231401
4885698572244
16587022444987
2319567402649
6231581337197
1569730285443
4847980348297
12252572031646
4431425874712
323080273285
32...

result:

ok 254492 lines

Test #36:

score: 0
Accepted
time: 411ms
memory: 41188kb

input:

66521 1000000000
1
100888074 724899271
1
383974339 525803786
1
177758589 746188897
2
43693161 944937876
190107805 328097669
1
368695775 645578381
1
45868643 945463129
2
35497597 487070702
280764180 520751991
1
513775132 662203314
1
675034678 810178893
1
202553257 457440383
2
215837481 534780308
2159...

output:

305388524146
45022864737159
10500954543849
8438533262456
9979743259505
10891764386746
4664517331187
22768261133015
21303458836208
9303196982744
1485429597351
9056671351860
25689271815594
21262334807113
21997538945223
4600752529138
22213030192759
27937024075201
4935426483271
13826917234397
2209475129...

result:

ok 300000 lines

Test #37:

score: 0
Accepted
time: 267ms
memory: 36508kb

input:

32773 821715347
1
164175311 554392727
4
242929741 561323824
123142278 793184407
433924283 611053664
141783625 656643810
5
188032249 555808424
117589857 174059366
292218302 339909559
595853685 796423732
258536063 409946214
3
461197698 660501754
130204943 729851049
229293561 292594636
5
113638599 3899...

output:

2403767902041
3952457478497
4219424576041
6921130818687
5804744297432
1975066807652
5505110911670
125711837119
6670873805557
13483818116043
6328129199834
7919749548120
5561471314066
7079261274207
3126792791049
4994414745336
436181846447
1036836581519
708458177153
1176489430394
4982965845456
16889214...

result:

ok 249026 lines

Test #38:

score: 0
Accepted
time: 280ms
memory: 37980kb

input:

33352 1000000000
3
459813064 681585307
340616124 676622546
11711445 912733259
3
532596838 790638350
273268662 752482101
45086207 847432666
2
559345080 933523030
255761232 569681246
5
479195731 684843831
523600630 733638311
329645549 670519127
44629253 328880643
65587746 374914231
1
351672665 7913953...

output:

597081461310
1278299205763
5674232764840
6136927831828
6722611799872
10173078126416
3640044578209
3699973517499
13775015909046
6421038243191
9778197280590
486339347256
2944327716762
521745440907
12586096772142
706809254977
2187258064338
6476947559854
3812230269532
7848120751445
11975611559905
438799...

result:

ok 300000 lines

Subtask #5:

score: 36
Accepted

Test #39:

score: 36
Accepted
time: 114ms
memory: 38168kb

input:

301 1000000000
300
863578477 865166395
261293731 262628986
290161866 292035987
31029640 32135494
288138979 289416854
321254857 322352244
163393949 166291828
897880953 899050317
840019366 842900569
100947276 102350870
520716771 522094941
820182602 822928836
766708508 769688128
727827782 728874133
740...

output:

996840913
213467673
996840913
350088722
393643222
660161043
23398481
83378757
386772057
550058707
116797789
66795163
230046137
430022213
50052816
646976316
223372288
443414533
153481147
43516132
10186037
656745708
93473524
443593864
613442576
306857640
606706973
613462088
456791451
276831487
1034634...

result:

ok 90000 lines

Test #40:

score: 0
Accepted
time: 113ms
memory: 37100kb

input:

301 1000000000
300
300066064 302323286
473632893 475766284
351370863 352221960
914819860 916333465
317977421 319127906
920520037 923283324
504830796 505586396
494369607 495452979
558040391 558539388
23365739 25905186
564630891 565459633
277441881 279789082
961207919 962159794
693338597 695347090
578...

output:

286865169
313364540
996793841
720065430
783551270
320062652
50110451
340091416
456818265
106730063
250074295
56771021
100124212
90126317
70034915
413435450
426731145
213397678
46770743
113477622
30125146
266748001
793374963
343416973
130072106
880090066
26828815
196784156
596947893
460085415
6752386...

result:

ok 90000 lines

Test #41:

score: 0
Accepted
time: 115ms
memory: 37680kb

input:

301 1000000000
300
436133849 439766906
399299656 399871397
987510123 987623863
87382570 87807552
948515445 949052052
596367083 597547004
838965514 843316163
505192505 507242632
813023000 816438712
680226676 681650508
241702689 242610357
903574024 904180573
293115387 293225805
965934333 967856315
359...

output:

375138342
196630758
480427492
72200479
226103302
192548720
405758667
18014460
276454760
287183968
7303408
148051928
324101075
70716872
167805126
79418501
87154832
328873671
90156751
401532551
18997429
2458843
110069678
86903655
870988
34835290
196364999
201922538
108740749
235174223
181778722
869036...

result:

ok 90000 lines

Test #42:

score: 0
Accepted
time: 115ms
memory: 37828kb

input:

301 1000000000
299
770778382 771390993
731130505 734282136
900324353 900756667
315720590 315879945
549885731 551694156
961870218 967237404
449686711 450724459
169164766 176907126
418234610 418840696
874086997 874800159
746489809 746815743
704004512 705083659
779639958 782291940
538072804 539490105
9...

output:

278151674
48664023
474375584
192834
89456431
315809268
464386665
92387184
365717998
311285027
11591638
42204183
161647182
166728915
160331861
116815686
458008311
11591638
185637145
210866239
134761268
3137894
49495155
157947203
6416710
216770354
112128268
54180198
20566729
15835368
202054033
4204761...

result:

ok 90000 lines

Test #43:

score: 0
Accepted
time: 110ms
memory: 37740kb

input:

301 1000000000
299
333948864 338012623
912826899 913391055
571148299 577968736
372988318 373399550
162424522 165729804
754997109 756545766
55958658 57190515
677609768 681027389
834938974 837016269
366716733 367166710
176358492 176855515
146676373 152623195
967011409 969970853
302962786 308603483
421...

output:

215116970
309596332
449007971
86708426
89020740
1378772
164417408
123121994
258650249
31734252
208339511
329295444
226562183
56266419
265427201
26290202
182058675
11508341
18364019
216120098
16779760
224579848
3856163
40562766
124790659
266181589
141282804
20226095
347296033
264493325
34033836
32337...

result:

ok 90000 lines

Test #44:

score: 0
Accepted
time: 52ms
memory: 29752kb

input:

301 1000000000
300
614330645 904777865
21671200 972465607
844511005 869900059
222039406 973766970
50412921 890784128
448643606 930527499
321278854 633891369
339898318 978093316
494050725 535513007
681208047 744770267
86200056 932879083
882937423 926179572
142953625 486908718
433164812 480712775
5911...

output:

10347846948
11800848772
17261653888
98905
10314234020
2957329058
4417151526
3039339968
7285236230
6570977671
6331232853
14679251466
8707228611
300284111
4990743980
7676381144
8350448209
7885156273
6425522914
4190367169
8020285333
14717882755
160647082
438592292
2582876959
4586484
9574940726
43663620...

result:

ok 90000 lines

Test #45:

score: 0
Accepted
time: 68ms
memory: 36576kb

input:

301 1000000000
1
1334350 998890869
599
971308804 975093823
759737391 761610435
787176304 787284902
816238240 816573264
858109281 860240492
920044373 921239817
343319757 345239835
346094920 346102391
736650483 736783277
577150165 577890956
184122044 185187782
314131298 314627686
204408708 204445102
6...

output:

235000647581
87000647581
299000647581
170997556519
27000647581
121001538193
111004629255
60997556519
73004629255
23004629255
127004629255
109000647581
43001538193
81001538193
79004629255
177000647581
73004629255
188997556519
25000647581
55001538193
17004629255
183000647581
103000647581
119000647581
...

result:

ok 90000 lines

Test #46:

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

input:

2 1000000000
90000
124621107 763212064
251817510 936472509
993219630 994601989
137121582 138175347
278276318 575480374
490851352 496516863
654522838 977035777
223624214 774171212
452916446 457640243
982885774 984407786
80264328 886909856
20220167 476582796
923495569 927815157
95304908 96679851
15446...

output:

43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
43866
...

result:

ok 90000 lines

Test #47:

score: 0
Accepted
time: 361ms
memory: 42388kb

input:

90000 1000000000
1
338316860 644977262
1
563229885 715913633
1
335134604 752347690
1
625869440 822316033
1
795020960 990410399
1
281092649 637534374
1
401749186 605375797
1
364028027 560879591
1
437100466 932728915
1
47282941 348181727
1
146320889 885304930
1
5931022 880672331
1
372980219 595366588
...

output:

53768648355483
23838206213541
54639890432191
54626071351229
54620783971213
54633457136337
53796086503560
53371216359653
47171932914429
47690622286737
12779024553400
14291140362267
54621717013982
53564336324001
34113438470190
14257801391203
54500354471647
52911934965281
46702212341124
28109074944513
...

result:

ok 90000 lines

Test #48:

score: 0
Accepted
time: 281ms
memory: 39944kb

input:

60079 1000000000
1
253782450 453522147
1
168581347 819446881
1
451623493 804648849
1
96689328 297947513
1
568567663 753006192
1
136248021 352134084
2
213716273 281499582
340303924 345505579
1
693448835 875475762
2
82796452 571095152
591684256 596522691
2
174711924 834329131
509836504 897647103
2
588...

output:

23748161791455
23808223741525
32703390861713
23671406800914
22277497154338
6528635850090
22309408468539
23045471979897
23766008116235
18678652901918
12146667312943
23700943591244
396327395474
23809301713385
38255070436059
20542266534480
1650256157524
20434443955493
29627140458924
3801589804354
21528...

result:

ok 90000 lines

Test #49:

score: 0
Accepted
time: 210ms
memory: 37224kb

input:

30059 1000000000
2
462069213 497789433
718311044 777370852
2
166968492 337050767
682764763 703100408
1
170223771 361271214
1
12437094 156663631
5
88712882 466784605
185303511 573910587
280556990 858685481
437877878 868470162
723102405 871554647
4
153331570 305826348
214959971 636146568
344643556 791...

output:

8819134597055
15467174865861
8807727903392
13167271964440
13246196492496
8432704137443
15473630461645
8808523951430
6478360832294
15410061508146
6159478112442
8832460910193
263765343200
5496440428082
3038791544438
11688312354684
8815867919342
7715984235574
8443541510153
7834972972137
10885661641327
...

result:

ok 90000 lines

Test #50:

score: 0
Accepted
time: 173ms
memory: 37724kb

input:

19004 1000000000
4
17206998 281766058
84488752 282994887
627425516 748672588
951308237 982130356
5
87890233 339680056
245855594 356952771
359686187 652998154
426238017 663778482
880913537 907711864
2
115260936 207032110
718881449 739560320
3
41956730 471715219
335629962 736275482
864030335 999290375...

output:

1099534056627
1991434504019
847269201976
528051945483
1659766599758
4374456430605
5022451902450
3742732803311
5944843968278
459717145972
1483415528185
3959600286689
5049192052556
873200004808
923403984856
1183434650393
4356588642462
2429113619294
627069567181
3937135819996
2841700935705
539008261647...

result:

ok 90000 lines

Test #51:

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

input:

18916 1000000000
4
346783099 470848200
559020259 602178066
577282980 661843175
680381683 823131053
4
47066782 148949315
252043225 637023874
401154833 671819033
784111616 989739428
3
8865129 502866987
265992679 807208282
335662478 930136515
4
200458018 317869777
299741514 395799404
370552553 42806770...

output:

3238729533437
777639478693
4391830958910
3352206627657
560413368584
3198338814211
971643878797
4464331123228
1356419370120
162750212568
2277431305786
1466513600403
2065619963790
5475585276731
456350584073
164290582872
1833082463519
5836737218669
1487059271239
2605671594492
2904728024118
270474999315...

result:

ok 90000 lines

Test #52:

score: 0
Accepted
time: 173ms
memory: 36968kb

input:

19276 1000000000
2
325514438 836447215
366949679 998648867
5
176147835 552851139
310657024 583334999
339031648 628759843
383618367 745869472
529066413 760323693
5
167007348 353080479
242762963 770910232
343271308 780138092
761154681 921974020
801679864 981937499
2
677641365 758709349
717559356 91317...

output:

6146626238735
5208726718183
4873849912054
938118247453
1286346562828
7432689413610
6494789893058
3271206192187
5962875763505
2875597358157
1937697837605
4557269367062
7671382629633
4795133220518
1525110132395
2462874638351
252144514610
8957445804508
1554320142865
3118850461637
4400353749055
35692884...

result:

ok 90000 lines

Test #53:

score: 0
Accepted
time: 169ms
memory: 36252kb

input:

18917 1000000000
4
29027499 231827499
75725779 470160321
757586713 886276634
839636169 955825903
4
25198161 123103176
128378821 281135131
292543311 728917163
831388778 932162077
2
170528494 174338978
447917091 918975216
5
67218787 110234236
524805314 529179462
565957537 794120654
676108363 928751425...

output:

8804900918200
2665479789262
5286329772885
8751033634475
1662657739
4470338018288
6411041892914
3022197488802
1803791271441
8818607269492
4471929186164
7545095018845
7546686186721
3075153377575
5566332577410
8822920352638
1687286902175
6406569732507
1210727151777
6408160900383
4642359006499
452270264...

result:

ok 90000 lines

Test #54:

score: 0
Accepted
time: 114ms
memory: 37032kb

input:

1349 1000000000
70
710840 12547216
12027935 14765000
45359588 56936295
54803263 117798657
62417340 127445061
79707220 155214313
116425661 157330890
123815671 163519836
127280759 169532931
128017177 169810531
157717367 176729720
175805039 191910573
180077045 214840008
190718287 253202862
194576606 25...

output:

10781653274
27537649262
48834402099
59936019762
23633004844
96602064710
75397807064
63999979984
62628635690
23755098026
20851554912
48087001866
56779694182
33221044656
55263078069
85944602073
19804272313
46717549969
79115920469
2172263661
163176343821
2181981715
38223322141
60040522674
16220655154
1...

result:

ok 90000 lines

Test #55:

score: 0
Accepted
time: 77ms
memory: 36532kb

input:

439 1000000000
131
7221855 26021118
11247662 27485090
13203383 43732905
19025877 60681483
31692809 66177446
57349733 78795904
60479885 87280104
65785454 102219068
68074326 104132708
84499701 104637224
86923670 114703218
88211666 115613399
89152491 124985965
91240046 125114975
92740268 126318040
1155...

output:

6987434367
15121381263
16016359740
6281405495
8180280367
14829169475
17044385632
16715485074
16046486922
13762775361
16709338979
17011264378
16922403923
20851435677
11187658535
15876670419
12309881163
14996141181
17282654034
11670577356
770601012
11290351428
17088373268
17470030210
13853389363
15874...

result:

ok 90000 lines

Test #56:

score: 0
Accepted
time: 252ms
memory: 39304kb

input:

65537 1000000000
123
15647797 26276884
24099356 26562597
25173015 35877256
25309676 35908612
25500436 40902791
26773458 49162342
28202078 60954901
28661059 75097034
39620318 84893746
40033859 89497884
41156937 99087857
44863583 112043683
45485113 136718814
47298165 139470597
73487680 179698537
77689...

output:

53611763750012
53611854446856
53608068353087
53610588088006
53609927617148
53609586268573
53609092687920
53612928948899
53613495033275
53611534068783
53613381067324
53607688772019
53613036369520
53610933955292
53608235078322
53608374640242
53608172527281
53607839953422
53612437672948
53608267316791
...

result:

ok 90000 lines

Test #57:

score: 0
Accepted
time: 268ms
memory: 40432kb

input:

65537 1000000000
122
1889078 25485586
11496455 42226678
22157707 49942564
28705187 54233818
30882333 57815041
34164017 66711429
36461936 72957299
51572963 73766466
55442614 74375514
56159030 89108667
61922084 94310000
68898461 112505745
72158317 144525759
79971387 149956563
81661858 153588290
822228...

output:

53637869918578
53639529230666
53641372757881
31141835439154
53638962084558
4738168997864
137879367
53641331054033
20976273887557
53642221046565
53643541777071
15294532151916
53640869184451
10748034134999
53643602621432
16254822803639
53639425323000
53640689714818
53637258583177
53638798658004
536357...

result:

ok 90000 lines

Test #58:

score: 0
Accepted
time: 180ms
memory: 36344kb

input:

32769 1000000000
203
5326613 6989434
11240161 14377000
13779338 22139081
15434449 23950904
17231890 31940393
27207939 51941996
32191753 52497542
33159596 58019894
42580464 62597952
44850480 62757913
45230030 63174191
46198116 69160794
51561702 72935802
51770120 75405691
55984600 81379904
59192416 83...

output:

25183360671664
25181881858229
25183922607430
25185847299285
25189780214763
25183054492530
25182993360633
25183916325357
25185601986093
25187260040621
25185187239360
25181910622090
25179597969445
25185901430414
25183056907042
25178957292291
25181419475036
25181545734302
25187943555472
25184475146938
...

result:

ok 90000 lines

Test #59:

score: 0
Accepted
time: 196ms
memory: 37956kb

input:

32769 1000000000
159
4043997 15813032
4653260 25706651
5918786 28045943
10032013 32672981
11735141 34624749
25060207 51490131
32417268 54929219
41516083 62429592
51911462 63030137
52654757 67285847
54621196 81839076
74937166 87933709
87836792 91197205
93455387 99682377
94609411 118012230
98599431 11...

output:

9565014061666
25189477100784
25192613131873
25190871788482
25194594158839
8483067490973
25192513226030
25198986522164
25195810219523
25195580099338
25191552686502
25194190712539
3633836239554
12408525239823
25197834538904
25194267561137
25196813205003
25199541197450
25197823984120
25191734178796
251...

result:

ok 90000 lines

Test #60:

score: 0
Accepted
time: 185ms
memory: 37180kb

input:

32769 1000000000
22508
7941 36860
11840 49693
32536 78269
33129 230244
55388 234880
71100 328210
216923 350020
270665 374416
333542 442531
401937 543459
431040 597063
453889 616546
466363 648376
486519 662874
505371 687189
540441 722006
546471 757356
548604 759419
718271 799734
764022 867368
789652 ...

output:

16245344572138
3845268927323
2344505645168
23069299954893
976651238900
13873747933176
15383144051876
15485518342846
5011473862202
12503706960624
22895565348851
13803877202931
10843522908064
7331309730304
14253686149422
14534465150101
2500589096229
7499478224060
18434865906175
13307864129258
19101343...

result:

ok 90000 lines

Test #61:

score: 0
Accepted
time: 163ms
memory: 38356kb

input:

32769 1000000000
12238
7253 140524
63909 537054
217983 660123
220115 680574
273045 696386
288998 724445
305871 725592
320089 731343
320248 745775
327501 953643
340695 979976
368382 1064144
504641 1089744
645762 1179463
761103 1254166
795006 1302445
952978 1330405
994231 1350719
999610 1410243
103117...

output:

25404844883721
25404841351451
25404841799945
6568362481570
12005269750160
25404838267675
25404844883721
25404841351451
25404841799945
25404838267675
25404844883721
22757528376427
25404841351451
25404841799945
25404838267675
25404844883721
25404841351451
25404841799945
25404838267675
25404844883721
2...

result:

ok 90000 lines

Test #62:

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

input:

32769 1000000000
5679
41411 176552
247652 366402
278156 548875
335930 598311
539269 765668
551045 1136585
577893 1442623
1053115 1584186
1157255 2083595
1396228 2370385
1422403 2987753
1479013 2997773
1701020 3311244
1813558 3367554
2080025 3540926
2086683 3831385
2117507 4012489
2287027 4122529
243...

output:

8866114982191
17502261207282
24970178131000
22226259473985
5928258601176
12072900482061
17579237493625
19121106818554
25792427126133
7837831676948
7403761428332
14854460283962
17001083917012
22956247140263
24607565754780
19687184806574
13906025114005
21165815610166
19956849285859
8523725595486
20823...

result:

ok 90000 lines

Test #63:

score: 0
Accepted
time: 342ms
memory: 43180kb

input:

90000 982085869
1
179524810 875559706
1
92250807 179524810
1
179524810 829939078
1
174617610 829939078
1
134740965 307079076
1
88486271 161925708
1
69733525 925328739
1
69733525 636015521
1
60348651 636015521
1
60348651 765045057
1
27056813 121765130
1
27056813 390141841
1
10242064 390141841
1
10522...

output:

23239903212239
67328490341467
77384867345187
16103581455728
48827961301850
258080530002
57543702853115
15937108657157
1562554272584
49733288617599
21544952445321
45644496238495
26548693025734
12616048240912
49132913175891
41296554181209
29371220155252
44130852156628
25316339391781
25610849730829
489...

result:

ok 76154 lines

Test #64:

score: 0
Accepted
time: 363ms
memory: 43372kb

input:

90000 1000000000
1
333333333 547672617
1
66250521 333333333
1
66250521 465238513
1
25056236 931530688
1
25056236 931530688
1
25056236 418031923
1
25056236 49949759
1
43637258 262128043
1
43637258 557428948
1
43637258 90598659
1
90598659 286554187
1
30589859 196412699
1
196412699 888189724
1
83297429...

output:

21835203235413
36307855764115
78711498993191
9003525125860
48206752048727
35173697223590
52142352568368
238064482025
8515402785198
9788907144898
23087099925570
71654063339712
1655460914373
42226541271628
53236317699104
8267490328438
9870899032594
41842410509949
32681487679742
2453156860095
569763887...

result:

ok 90000 lines

Test #65:

score: 0
Accepted
time: 348ms
memory: 43564kb

input:

90000 1000000000
1
0 415553182
1
107270602 584131108
1
187815781 682910162
1
465067084 477190946
1
380235812 829564774
1
2910518 550208988
1
403974458 651861534
1
207142585 902561621
1
805747877 876890420
1
864459534 983675311
1
256425317 338643061
1
169211971 925741293
1
169935144 580249365
1
14117...

output:

52098832885540
45317869425800
89998999999999
40758353427541
14261729630026
28974702852751
6267790739662
32947570447743
14599335395444
47048009620041
13189306165031
54631166840663
26375686398620
960815014311
57640667295823
42343245099178
13046800100091
11785120730656
30204293884377
47113472809218
511...

result:

ok 90000 lines

Test #66:

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

input:

5377 1000000000
2
206704390 584382869
93188229 845328205
5
130951514 303276556
722229647 914871908
368877294 661919730
631654845 815063719
311071515 647999522
5
405937611 654764095
97755729 819204257
299468032 729198000
406024030 645381618
131873468 911363840
3
216094854 942167351
349921135 79510818...

output:

1242453978566
213972834867
2611358026078
466656317301
2183970876363
1386748517435
2315757062318
817803676465
627667318976
2823372211603
619307329283
1162546456253
1625323301736
2028642412984
174106261582
1948132405779
1971099048645
956138944652
420983907056
2417934664308
124582844514
1649127640716
5...

result:

ok 90000 lines

Test #67:

score: 0
Accepted
time: 40ms
memory: 22192kb

input:

25 1000000000
11108
441825184 700261712
936426177 970037482
258135376 913962309
264702236 425472726
171439443 708720928
344860085 995984453
756417069 791921135
140896076 252225678
236456948 463663887
62146708 178352523
863065229 966315029
462204176 480295033
59475518 209455434
631769300 647120582
39...

output:

820018730
589127360
16276809
68635
78143597
1334534575
2036906065
305239214
1199697018
408132305
10878796
1600493261
898713664
322777
4134630
37243030
763284214
1765617892
129760113
385880247
313339197
676719
2148277518
47410532
77138027
676719
654986705
1534105225
134267066
38008
2961544
17201789
1...

result:

ok 90000 lines

Test #68:

score: 0
Accepted
time: 51ms
memory: 26296kb

input:

2158 1000000000
70
59213557 907491136
283552171 610100248
326134207 723747865
785160275 858177203
168541324 235881740
19596608 568634771
295238396 425567801
228622051 881835819
13427339 786773618
196430796 617485668
165542488 427306508
270293670 942512926
456145094 731606783
680234277 691762940
6695...

output:

100904344155
150020760595
269809925895
148189905078
70590730052
57116189291
49201230804
128351241999
125567929619
5631443679
129202992013
22703892153
47318097449
9227966534
83157397037
36475920740
31614196165
75719269446
273895738291
21829337136
14161384457
2634738
306970634314
34337864819
185029800...

result:

ok 90000 lines

Test #69:

score: 0
Accepted
time: 37ms
memory: 21820kb

input:

152 1000000000
31
126317399 950827698
525397352 576623863
260375341 964130801
357128417 745841287
2771899 943721506
155003935 448718421
151662168 188181086
522813417 558186651
111497427 514986497
492852 447253697
200387437 821450188
246753003 350204903
343809312 813498169
453136511 454743728
2888234...

output:

3686406359
19563728411
19087306676
11710426256
17840342449
4387712510
19798424415
6945101918
2554039538
9278828762
514552456
6507301815
1465615911
14787350709
20900449572
4652348210
4767519899
3317531641
10838724730
17731455808
5993985763
9973531891
10667329910
213059235
8502989074
13969835819
12585...

result:

ok 90000 lines

Test #70:

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

input:

426 1000000000
49
110642381 433000750
298872676 516356239
796127568 982225117
76453992 295703417
48843499 275840964
184738668 833875036
228268657 483622103
75414980 586889261
92030584 638488751
285724192 370425481
421320416 916807155
93003819 533544398
74773073 979214772
740472018 870318410
34963424...

output:

3883839583
6259482349
6281725426
2383189751
29677084925
665926182
24007001202
30989600464
6127874805
9522423828
22096620032
25991175882
16265857184
4631228556
8543849011
26496762850
22318405489
3648619807
34556606570
20012523069
3891977052
2210455295
502846047
23650830334
5546815575
11667848017
6006...

result:

ok 90000 lines

Subtask #6:

score: 10
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #71:

score: 10
Accepted
time: 234ms
memory: 40080kb

input:

540 1000000000
185
488454816 490688658
515880182 518147238
266264030 270193516
504037560 505540657
850747400 853584593
44792830 48363310
602304591 604044233
921301260 922514992
67547938 70110134
260491130 263196238
605686361 608971712
659676141 663120642
650771448 652270743
250976919 252198802
40797...

output:

1919058224
1881643991
2908214198
1627129161
486642691
849209110
1649132511
1075769595
2383945015
1459750751
2356952009
470463376
1497577371
443310574
1475805813
686549017
1616768727
449050952
1108374959
1621754708
1184365700
1459610220
1659655864
49007981
1438184421
292120335
1394850227
65060744
448...

result:

ok 300000 lines

Test #72:

score: 0
Accepted
time: 234ms
memory: 39736kb

input:

540 1000000000
185
54799168 59234126
677899998 681061700
514107846 517050368
229020706 230993202
470791569 473255457
22875053 24970200
341086059 343328885
115936541 118897892
585406238 588468556
99918677 102693107
250108997 252259095
882398848 885747893
785868206 788455798
769700327 771412215
845415...

output:

2816588569
1962255364
2908320130
448771025
762273327
32741992
2367991468
670441246
1513640745
1427362257
1178662675
286659683
1659763582
881616195
1324548855
2405465988
513818299
400101722
194881429
2173256006
211147603
1654205312
1697728320
1006028479
1551792951
1162306154
448856600
421862648
71391...

result:

ok 300000 lines

Test #73:

score: 0
Accepted
time: 234ms
memory: 39768kb

input:

540 1000000000
185
345013756 345672247
662508424 664107937
215008319 215621220
339732551 340339580
839624672 844154049
189424172 190028658
502171024 503563536
241062815 245183090
251385735 254345291
154658126 155840202
774587153 774937900
358308467 361496203
55017806 55799157
979049812 980106291
412...

output:

1159976466
473764467
1411100268
516629901
1094859473
601790146
1146221694
330247923
675861682
476418775
299418407
115126710
88185035
1268186378
155397177
200868231
257147305
312980111
663725036
647660354
333701004
1281091973
500294227
557651077
174691831
627495198
225642148
1001759346
1163543272
204...

result:

ok 300000 lines

Test #74:

score: 0
Accepted
time: 237ms
memory: 39844kb

input:

540 1000000000
184
660901704 671725365
154647857 159271081
13865163 14885105
584900345 587460597
390059406 396722539
202458710 204230253
875712332 882433204
919895260 927962838
171732277 174857132
290023723 294645015
22969599 32435811
512082182 513426248
130671568 131662301
638552963 639847890
25689...

output:

1192932394
1298722770
1404818748
745836260
794023229
531669431
496701111
73039604
351541651
223889241
1229826072
243168420
1083274932
1150097925
342499764
540678985
5818804
295128471
1402139
1163953526
257495158
597086936
144130159
355518718
216587010
195161304
281685783
833875210
57261185
52923369
...

result:

ok 300000 lines

Test #75:

score: 0
Accepted
time: 245ms
memory: 39712kb

input:

540 1000000000
184
491133974 491590328
786537737 787267335
759371887 762837635
54351630 55103567
73349807 82499117
822490699 822752173
503143277 504371064
450314662 450900221
667692602 669259109
131213483 134371452
407781868 408426938
764020822 767894605
792046173 798606969
67135700 68751119
6369738...

output:

1357867319
728920651
1386636801
16855285
72805491
658631365
130331781
1004369760
734201862
137210889
4856628
95427565
1012027143
58891006
216293148
405764965
568325609
345967218
790239472
198553402
11817947
850
759217176
787637221
91970532
202811647
137243198
103451984
46593729
672493452
271620169
2...

result:

ok 300000 lines

Test #76:

score: 0
Accepted
time: 102ms
memory: 34360kb

input:

540 1000000000
185
134726091 454273130
669424806 729150726
76345194 585482224
991438669 993048303
452510144 575885092
29375753 29739611
463847700 598231643
509316484 790868594
4463284 976957147
11693359 648466156
107465655 120350121
112159432 307326208
833581504 939759577
185590192 833419854
1572745...

output:

37790043582
37840806518
40172716033
6231769263
14929268027
13394288924
27784057949
38885564772
29799570663
38644634929
3569064018
17946468828
9010555076
22720141337
6708661879
15878631396
13985504183
18048521930
1459483739
2062947568
7652342316
2450830410
7388395553
25569623813
9205764555
9137380566...

result:

ok 300000 lines

Test #77:

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

input:

540 1000000000
1
711266 999722032
370
565553478 567324961
737234517 738353657
360074226 360699653
854159661 854211275
514880319 516072526
904748958 905799303
645245915 646511951
75308597 77820867
724522670 725632293
698096805 698437681
112571213 116016962
790337129 791304224
607038757 608507066
7469...

output:

283003400780
184999010766
538999010766
278999010766
25004766358
53004766358
307004766358
100999010766
3009156372
77004766358
215004766358
21004766358
37004766358
27004766358
101009156372
35004766358
193003400780
415004766358
13003400780
70999010766
25003400780
53004766358
203009156372
185003400780
3...

result:

ok 300000 lines

Test #78:

score: 0
Accepted
time: 384ms
memory: 40592kb

input:

770 1000000000
130
641827776 643460168
695585485 699873816
949927923 950780795
657000521 660395086
487716999 491391703
909090237 912079216
326336238 330297709
600820860 604024129
185617073 191866650
370820965 376479699
734433036 735614993
85132887 91493457
310501163 312965320
679748460 680806184
616...

output:

4092591694
2469602120
5908306249
2377294245
1262116676
2984718271
2754701332
2015729111
2954331007
2355024026
2477748261
4177328979
169713030
915628641
1031009539
177064306
3700552187
3754085840
2577329027
554130973
46822036
3315938615
3715653358
2346359966
1485019271
1438870266
3523377842
69500817
...

result:

ok 300000 lines

Test #79:

score: 0
Accepted
time: 398ms
memory: 40432kb

input:

770 1000000000
130
310753346 313595358
915677937 922528845
501544916 505592994
518034861 521514284
824598453 828969347
808894565 814821714
595310517 599182635
86818778 89530723
188331587 190921131
57651657 58287723
572322930 574219883
849561275 851858001
125659965 128909034
448641489 452694405
62127...

output:

5323685305
5308411949
5907933280
2207916166
4377331480
3476985219
3185066722
2862242344
815584239
1646698373
2992697731
2631347065
1454974395
31144240
2184889051
431000301
2154295558
1231021131
2954224234
1254468483
2138824996
2777145399
3769729500
638632667
3492713725
3439428329
1562022439
25932846...

result:

ok 300000 lines

Test #80:

score: 0
Accepted
time: 114ms
memory: 34776kb

input:

770 1000000000
130
963838423 988549892
40785556 168522093
772308848 932649955
698311872 912978770
257089244 398803163
150074201 313126496
537645802 686863991
49718095 213649467
394139046 820088815
101582889 288201382
35601784 567574552
623539925 768295615
321117222 448343977
241239824 945584658
1725...

output:

56858868507
26513280458
69657920330
28373936157
15610128950
26393088505
21040815433
52872761486
32452032464
15089581489
39105517081
5702276317
5538740632
3723892037
11374685223
51001228663
10347320281
4642899190
61795153331
15356863116
39821528579
46708481702
33244303352
11001345831
10319943557
1698...

result:

ok 300000 lines

Test #81:

score: 0
Accepted
time: 52ms
memory: 32124kb

input:

2 1000000000
100000
215106028 312181974
160310109 599214313
655477774 664765923
41064217 527505828
205091412 816310605
839883581 846091196
639998698 648585146
69305237 534764404
862699685 866902281
40957099 43065638
657783918 958409827
224870024 349508454
563825838 571753677
19390334 261748626
28660...

output:

720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
720
...

result:

ok 300000 lines

Test #82:

score: 0
Accepted
time: 251ms
memory: 37864kb

input:

21970 1000000000
4
132997934 156990059
294584258 392155349
333765999 612982422
447559091 771458751
1
276953671 666028438
2
485871313 756856188
535766633 839863214
2
576740567 769671763
645597484 889171008
3
80885306 163659190
184608004 715400325
845906601 858170173
3
454138551 665966556
672397040 69...

output:

1004493017948
4970776395931
157158476794
139501062979
3340699761423
133528896714
3013287701250
2518409068153
994221501361
492019289145
625067923001
1709713294142
1544243641227
1528754789602
1832908499530
399141372725
1836588484623
1316591617111
300975816379
2016440792480
1306437497471
4531070100876
...

result:

ok 300000 lines

Test #83:

score: 0
Accepted
time: 255ms
memory: 37384kb

input:

21227 1000000000
2
706779811 935474040
776181734 969523323
3
75176977 746258098
279234634 772269232
609560761 815033798
2
234372736 247611514
237616585 758397726
2
247372162 253428905
253294139 860358266
3
84348888 362257966
270731043 800462043
833584991 996057067
5
31539360 404474768
261510507 4235...

output:

318905606073
2902628945888
3996903418144
4029013820893
1103189639682
373239305234
520223874487
745673091150
1134518105285
4526181442311
1147806242254
1918555241610
1039036216257
3181498442138
4425023366
273519703652
1971413833281
2203130166168
3198368313418
2769607436947
1160662537684
1532672861973
...

result:

ok 300000 lines

Test #84:

score: 0
Accepted
time: 238ms
memory: 37520kb

input:

21277 1000000000
1
248524462 975910027
1
238989181 256702296
4
167757568 436855153
312464589 890090202
402781171 899092030
851353765 916102870
89
6796027 29348425
10193300 30048385
32965289 46004017
37455383 56493738
44993008 67523985
45333428 92846852
47671285 108316871
78630751 116042121
80779522 ...

output:

1598747920276
9608337035695
6950694654808
8549090330489
4343262986942
5941658662623
2607453443163
1403167860029
779516755029
10177856766445
1441647178110
3040042853791
5509386233646
1819463285630
2901954565780
2699111904169
320595496628
1278939883481
3258648160431
7270937906841
4663506238975
1761890...

result:

ok 300000 lines

Test #85:

score: 0
Accepted
time: 258ms
memory: 37792kb

input:

21108 1000000000
1
131112179 513778787
3
128440921 252086238
249524049 784266090
830538812 902578682
5
221037675 448803913
321731336 636520021
429891275 717382140
458920566 855412903
556965505 928772015
1
433583016 458505973
4
124531098 204005661
163643064 247461791
295907259 486210777
500497446 974...

output:

3367527076822
347169963878
474434687191
8687238885421
1919633238272
7071559901375
2133646228201
5024369178141
3678603782728
9494355315010
4323973499664
8788775334902
8775194285385
8798477141883
1334121542765
8459906670769
1377132384783
8495217064539
7630005704701
3288546396587
10240781662355
5508661...

result:

ok 300000 lines

Test #86:

score: 0
Accepted
time: 169ms
memory: 37540kb

input:

1615 1000000000
77
9325731 50582450
11315227 50688535
19962318 61973677
38930699 73711004
53282072 113643558
54739854 124972952
57211597 126458719
86578320 157999113
87074822 197735010
100927938 202471115
128857466 227129034
138322734 232747036
145717393 236637834
153409102 243432306
156237105 25427...

output:

42678816135
131264462784
16974004728
63299107909
67612627118
13849224867
166925356232
154506899539
64281041889
102931127169
31581715300
67056413600
233525868735
40998919130
122821869176
162713511241
63299107909
169874033069
2968702159
141643256555
177299081324
143954772287
7253437645
124454055350
89...

result:

ok 300000 lines

Test #87:

score: 0
Accepted
time: 137ms
memory: 39164kb

input:

493 1000000000
241
3692155 16425049
14743434 18691552
17468115 32900103
19494696 35606597
20229055 38305268
22539884 41493706
25258996 57295213
30545892 62334117
31024307 67179810
35393511 69231720
49370549 76315670
53873010 88910557
55332982 90891858
64887282 92318629
67641056 94358391
72818860 945...

output:

17843999479
8934088999
17190366120
11005607071
17286596406
21740829487
17349563750
17308043232
17091416170
27147767610
17541952573
14426554443
17646447999
17002766982
29991870007
31041790165
17695958867
15724165753
11413983222
25887857899
7897893830
34178336039
25271755045
8904154697
17637237716
172...

result:

ok 300000 lines

Test #88:

score: 0
Accepted
time: 309ms
memory: 39144kb

input:

65537 1000000000
166
445683 13231284
3102080 19616145
6506654 27377226
11774676 41448159
22158478 51223094
24696735 51288871
31225080 66737576
48054176 66831095
48622839 83829070
54292801 85357086
55852958 86123240
57151147 89380904
58529685 93180395
61551013 99022253
64562910 103732885
67964954 108...

output:

53194909107981
53194092786049
53201677670086
53196734573844
53198499353302
53194968158286
53199011344665
53197014875125
53194989727636
53192726225318
53197264301151
53203191963639
53198147335444
53198117647772
53193667576062
53194761226413
53196675113426
53197679072270
53194667262532
53200380451194
...

result:

ok 300000 lines

Test #89:

score: 0
Accepted
time: 357ms
memory: 41680kb

input:

65537 1000000000
130
2404441 19612714
8269606 30409873
18484828 32486380
27223665 37445125
40082599 44849082
40657259 60140841
47230307 64133538
51731025 72428562
63189959 79343569
74327106 84055996
77470476 85982375
79581166 87940477
82463235 92959178
89661694 94373111
93349266 104455322
100027419 ...

output:

53085244268170
53089569228928
53088537505949
53090874796464
53088785366246
53089789029337
53088954802816
53084618281863
53090426843305
53090902447914
53088069619627
21348402469005
53090991399677
53088541339408
53089859466027
53092382947484
53094352758649
53089254483459
53087574186377
53093847972160
...

result:

ok 300000 lines

Test #90:

score: 0
Accepted
time: 231ms
memory: 36436kb

input:

32769 1000000000
254
1315654 4232336
4098048 8754454
7129895 30233517
8679165 38617187
9204436 43601424
12884566 50179238
17074337 55156072
18172555 61346997
22232621 67045479
32773182 73774952
35429504 86046582
44072220 87206641
45372774 98074845
49444558 119415944
55905056 126250023
62787902 12949...

output:

24785131880214
24789782031424
24788254707381
24789002152634
24790384794410
24790338737792
24790045598777
24787861349690
24785118323805
24791772729730
24789969349136
24786665353553
24789030489056
24789542583972
24788577592892
24791213894421
24787088880109
24790070709101
24789944500778
24787286670665
...

result:

ok 300000 lines

Test #91:

score: 0
Accepted
time: 254ms
memory: 38400kb

input:

32769 1000000000
234
2128524 4037315
2259590 7658241
4920918 13023146
6480649 14366663
13924008 15667344
18109737 22623710
18660614 23872447
20262304 25172442
24208421 26522584
25223595 34044257
27972044 36264738
28551027 38467006
40309032 46512166
42687106 48757619
45607715 56890566
46392255 570950...

output:

24848490440930
7374296932860
2536661587218
24838588536284
24846129692966
7850672984207
24840377240649
24846211468628
24838943332824
24841745192506
24839480782321
24841563246737
24843489714988
24846515376381
17355724624981
24843901338160
24840958492428
24846983711925
24842496222568
24843628117416
248...

result:

ok 300000 lines

Test #92:

score: 0
Accepted
time: 261ms
memory: 38084kb

input:

32769 1000000000
30613
15382 29509
28181 85911
79746 102087
87742 275819
99800 281636
132615 327366
171811 345614
188983 392737
264757 429018
279113 456864
307932 493971
316408 497624
346456 546472
366527 678789
375342 731447
469377 836062
552369 886274
581096 903633
618959 925872
715489 959091
7654...

output:

6856608807262
18382540813522
3401642957167
2659828452697
8513216206201
1299982463386
2852776919773
3189917682420
16409692562136
16020554377799
18223241194696
14073565688225
24792617282474
9154397314565
6835250124462
19041889780666
10370958383483
8030576412538
14233532968735
24792617282474
2090143248...

result:

ok 300000 lines

Test #93:

score: 0
Accepted
time: 243ms
memory: 38292kb

input:

32769 1000000000
15141
67721 197893
72318 237302
85210 373356
111328 487497
151357 543359
191910 555923
395236 601973
475555 684628
505912 737256
563577 778531
608747 846975
646767 852050
663943 882408
890307 922436
893939 967747
947513 1240889
1331808 1427727
1370674 1567064
1387339 1698280
1390104...

output:

24770452294656
24770453389452
24770448088936
24770449183732
24770452294656
24770453389452
3729752314695
24770448088936
24770449183732
24770452294656
2116722524382
2127959128987
24770453389452
24770448088936
24770449183732
24770452294656
8702509413611
24770453389452
24770448088936
24770449183732
2477...

result:

ok 300000 lines

Test #94:

score: 0
Accepted
time: 262ms
memory: 38456kb

input:

32769 1000000000
5691
363114 590947
846951 872953
955776 1430554
1233437 1526382
1384161 1597849
1620872 1895075
1722928 2479495
1897564 2601101
1941303 2888492
1949037 3308392
1977015 3339368
2246817 3840964
2461158 3917366
2603696 3998090
2629911 4051444
2646446 4458412
3007425 4486417
3078805 450...

output:

3184452192374
5949359772377
14655859256547
3719183730070
3943696908225
24630307041172
22094275132912
24630320849357
21254534945870
24630249539616
13108951180418
24630308998418
22393091107636
17265951875562
24630257571978
12129465548434
9275405099207
24630270683733
22338741311327
9825123192810
246302...

result:

ok 300000 lines

Test #95:

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

input:

1626 1000000000
2
566771644 797651868
210104300 920051103
2
258968221 520782269
538959381 754177324
3
579253407 941859927
192531837 341250422
16584112 983614159
3
662413791 956773524
148828243 291041309
489860334 496357731
3
212083392 440185471
432418661 588896983
955974501 984881793
4
308277611 749...

output:

672456647301
88688409905
62215051245
157144035979
254743511992
55260896177
520506204127
171683208568
533980876715
119405173341
322074000348
758187708790
842849878359
512252027258
590279695839
461562331000
278849390275
321114276214
345274101149
33766082707
265493600031
395445355432
18862399655
151502...

result:

ok 300000 lines

Test #96:

score: 0
Accepted
time: 82ms
memory: 25144kb

input:

23 1000000000
54
99127129 713047861
218471286 524916850
348376113 505105286
258383433 603347256
259213976 324260931
408084204 907065646
263231067 874637793
407552716 479066576
340753179 828406952
103779946 299346838
505728343 667555977
187537958 353043561
240533691 995494094
158872036 740487386
3352...

output:

2692122112
328459326
5146493518
2015723979
2282838900
614877946
2262932689
2514396681
4557422936
3397078449
261333866
179243835
10505059
293149103
3139923942
1253687186
1410001534
2015723979
1785781652
20573156
1498272758
337056653
4828
2283700954
3199599636
46707270
302968221
219313950
3200833
1335...

result:

ok 300000 lines

Test #97:

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

input:

2513 1000000000
77
464915645 906852283
52728876 310335994
419081644 512545739
611891467 906971252
437444903 544692932
8306641 712533394
88846719 601033924
160112391 220234924
123073380 600807686
442903145 866964365
42233702 251285091
12674581 465618793
20023041 857366110
325073048 658101391
56921698...

output:

141845363703
337514048110
155001967763
132182268525
20290768038
355521852140
123090166512
50799937698
208996522760
27014844509
55156591051
7474860920
438806978831
40530139285
146036087006
3911977646
58537522796
67278681188
132198831127
52351486593
14272011
266081025362
1874184808
422040799284
363487...

result:

ok 300000 lines

Test #98:

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

input:

262 1000000000
23
671390675 853975793
88792603 858109281
80866815 144975579
413224301 673066570
713998043 902018317
615272227 734990523
74536038 563063090
333114784 656055693
327644531 544750321
156686319 650427366
20852089 117757760
935631221 954167977
23330357 286045793
757301700 912986981
2059894...

output:

21915028769
1208700549
8498547391
11618483106
12513027718
2221210266
12087442790
21873963400
20278877304
3182431127
16154386668
3407795677
36512082796
33103400465
3960146305
19419844583
11336745941
24472655560
15200159014
94414791
11115135315
11812471641
24056729476
11032712768
28944060106
381346757...

result:

ok 300000 lines

Test #99:

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

input:

506 1000000000
99
32750770 486397235
516417575 751777266
377495159 712688301
852411996 892976266
448787083 985540808
430700627 784231424
60018908 451338501
427534061 556608730
599625316 807627317
318350822 866061320
18562107 95773036
137960804 648768147
142687881 422454524
37015582 134883201
6735013...

output:

3833945394
18474721007
21307516642
935353502
19348635459
1631881363
15046026870
12651591592
16675030128
31288965528
830704
40281360165
22605601521
38476683654
18443813773
21002851820
14879485612
9763527227
6561874967
8622967975
28994401945
20710043035
27751754712
1975757585
669275284
703600668
22155...

result:

ok 300000 lines

Extra Test:

score: 0
Extra Test Passed