QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#334114#3304. Interval GraphnKessiAC ✓466ms156072kbC++142.8kb2024-02-21 09:48:592024-02-21 09:48:59

Judging History

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

  • [2024-02-21 09:48:59]
  • 评测
  • 测评结果:AC
  • 用时:466ms
  • 内存:156072kb
  • [2024-02-21 09:48:59]
  • 提交

answer

/*
世界の果てさえ
【世界的尽头在何处】
仆らは知らない
【我们也无从知晓】
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <random>
#include <ctime>
#include <queue>
#define pr pair <LL, int>
#define mr make_pair
#define LL long long
#define ls tree[p].L
#define rs tree[p].R
using namespace std;
const int MAXN = 2e6 + 5;
const LL lof = 1e18;
struct node {
	int X, Y, rid;
	LL W, Z;
	node() {}
	node(int x, int y, LL z, LL w, int id) {
		X = x; Y = y; Z = z; W = w; rid = id;
	}
};
priority_queue <pr, vector <pr>, greater <pr> > que;
int n, S, T, pre[MAXN], id[MAXN];
LL cstmin, flowmax, dp[MAXN], del[MAXN], flow[MAXN];
bool vis[MAXN];
vector <node> v[MAXN];
void read(int &x) {
	x = 0; bool f = 1; char C = getchar();
	for(; C < '0' || C > '9'; C = getchar()) if(C == '-') f = 0;
	for(; C >= '0' && C <= '9'; C = getchar()) x = (x << 1) + (x << 3) + (C ^ 48);
	x = (f ? x : -x);
}
void add(int x, int y, int z, LL w, int id) {
	v[x].emplace_back(node(x, y, z, w, id));
}
void addedge(int x, int y, int z, LL w) {
	add(x, y, z, w, v[y].size()); add(y, x, 0, -w, (int)v[x].size() - 1);
}
bool spfa() {
	for(int i = 0; i <= T; i ++) dp[i] = lof, vis[i] = 0, flow[i] = lof;
	dp[0] = 0; que.push(mr(0, 0));
	while(!que.empty()) {
		pr x = que.top(); que.pop();
		if(vis[x.second]) continue;
//		if(x.second <= 5) {
//			printf("?%d %d %d?\n", x.first, x.second, del[x.second]);
//		}
		vis[x.second] = 1;
		for(int i = 0; i < (int)v[x.second].size(); i ++) {
			node y = v[x.second][i];
			if(dp[y.Y] > dp[x.second] + y.W + del[x.second] - del[y.Y] && y.Z) {
				dp[y.Y] = dp[x.second] + y.W + del[x.second] - del[y.Y]; id[y.Y] = i;
				flow[y.Y] = min(flow[x.second], y.Z); pre[y.Y] = x.second; que.push(mr(dp[y.Y], y.Y));
			}
		}
	}
	return dp[T] != lof;
}
void prep() {
	for(int i = 1; i <= T; i ++) {
		del[i] = lof;
		for(auto j : v[i]) {
			if(j.Y <= i) del[i] = min(del[i], del[j.Y] - j.W);
		}
	}
}
void Dinic() {
	while(spfa()) {
		int now = T; flowmax += flow[T]; cstmin += flow[T] * (dp[T] + del[T]);
//		printf("????%lld %lld?\n", flow[T], dp[T] + del[T]);
		while(now ^ S) {
			v[pre[now]][id[now]].Z -= flow[T], v[now][v[pre[now]][id[now]].rid].Z += flow[T], now = pre[now];
//			if(now % 10000 == 0 || now <= 10000) printf("|%d|", now);
		}
//		prep();
		for(int i = 0; i <= T; i ++) del[i] += (dp[i] == lof ? 0 : dp[i]);
	}
}
int main() {
	int x, y; LL z; read(n); T = 500001;
	for(int i = 0; i <= 500000; i ++) addedge(i, i + 1, 2, 0);
	for(int i = 1; i <= n; i ++) {
		read(x); read(y); scanf("%lld", &z); addedge(x, y + 1, 1, -z);
	}
	prep(); Dinic(); printf("%lld", -cstmin);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 64ms
memory: 116460kb

input:

3
1 3 10
3 5 20
5 7 30

output:

60

result:

ok single line: '60'

Test #2:

score: 0
Accepted
time: 50ms
memory: 116216kb

input:

3
1 3 1
2 3 2
3 3 3

output:

5

result:

ok single line: '5'

Test #3:

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

input:

5
273688 490724 141869495469
154210 248799 742530996682
149091 491274 531295833012
174801 345648 278781521855
102024 399466 621084696102

output:

1505485188253

result:

ok single line: '1505485188253'

Test #4:

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

input:

5
105810 416405 592884319111
68883 461849 250489784736
128007 390711 236479393395
110994 160261 671859872475
39895 354649 821557846804

output:

1493417719279

result:

ok single line: '1493417719279'

Test #5:

score: 0
Accepted
time: 73ms
memory: 117240kb

input:

5
74034 352895 387389006450
128646 447773 985594949211
116692 479464 753465491369
88207 164196 460965261831
310907 348457 244166716943

output:

1739060440580

result:

ok single line: '1739060440580'

Test #6:

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

input:

5
136223 315153 624871957613
123513 430694 514457730848
144122 163401 180633227331
70425 457509 583010340443
120858 358890 332106336020

output:

1207882298056

result:

ok single line: '1207882298056'

Test #7:

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

input:

5
32831 184060 188789421601
171427 329018 209530344935
161895 313664 844808531262
75336 382835 990150112615
368344 494450 383137311031

output:

2218095954908

result:

ok single line: '2218095954908'

Test #8:

score: 0
Accepted
time: 57ms
memory: 117352kb

input:

5
33097 167528 56416700595
78929 101983 55562283422
50281 247721 72636194105
57340 339774 753069033730
197700 361406 203188153213

output:

1012673887538

result:

ok single line: '1012673887538'

Test #9:

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

input:

5
136258 419364 970361584457
174267 423756 981896731618
218696 320621 799128240377
277844 388844 345834192912
326149 436675 517068146274

output:

2298093118269

result:

ok single line: '2298093118269'

Test #10:

score: 0
Accepted
time: 56ms
memory: 116968kb

input:

5
333403 365451 537561752876
244632 361560 741776349264
2218 229609 10595278802
337055 425647 647565847251
318064 408347 468418159265

output:

1399937475317

result:

ok single line: '1399937475317'

Test #11:

score: 0
Accepted
time: 53ms
memory: 117816kb

input:

5
305912 356193 234556428936
34253 146174 554916208323
354663 382256 501013406841
45319 313082 761965038322
89846 114859 406147662810

output:

2052451082422

result:

ok single line: '2052451082422'

Test #12:

score: 0
Accepted
time: 58ms
memory: 116308kb

input:

5
10484 386673 674957728098
123005 450911 341635545468
199576 219764 182440191590
8228 169007 33905834946
145538 211849 446485748684

output:

1121443476782

result:

ok single line: '1121443476782'

Test #13:

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

input:

5
196155 216384 215933148505
318876 435000 353829017744
122721 398621 58734912743
533 238849 856486333719
66200 250933 4453945996

output:

1426248499968

result:

ok single line: '1426248499968'

Test #14:

score: 0
Accepted
time: 57ms
memory: 115440kb

input:

5
91236 168330 90354269558
218682 390889 191205075883
221683 493083 497918647229
117474 419937 358256123269
416422 453062 554087430692

output:

1333565423362

result:

ok single line: '1333565423362'

Test #15:

score: 0
Accepted
time: 63ms
memory: 117116kb

input:

5
237922 414694 492791392236
200810 295732 703837767479
80849 423897 910310765595
225197 246617 253402130446
179804 218858 140534479355

output:

1614148533074

result:

ok single line: '1614148533074'

Test #16:

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

input:

5
41929 300931 944331027727
172666 330417 160847432302
96286 113241 63372527926
40867 216156 223392679613
2594 364462 733811708804

output:

1678142736531

result:

ok single line: '1678142736531'

Test #17:

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

input:

5
149362 275221 743901732699
56820 63687 656767349940
48803 416252 30388045831
10253 490848 438410675855
95963 258763 737529907846

output:

2138198990485

result:

ok single line: '2138198990485'

Test #18:

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

input:

5
263018 373835 428350273686
29375 111905 375640479584
25231 174870 832328659881
256277 346665 898287217911
238721 460504 367473312117

output:

2534606631062

result:

ok single line: '2534606631062'

Test #19:

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

input:

5
403708 447891 992157496819
111375 353523 122135869693
229322 423973 20556361975
261462 369014 103826845743
273450 472665 919831236649

output:

2034124603161

result:

ok single line: '2034124603161'

Test #20:

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

input:

5
377042 471720 754973059247
125073 417498 462936493167
36335 122931 885958721333
9163 208425 64065945078
248923 445028 340586669747

output:

2167934218825

result:

ok single line: '2167934218825'

Test #21:

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

input:

5
50175 332963 803967616817
435270 493076 849028012433
148028 373266 769209798414
359249 396083 298323538571
223698 417563 515736691873

output:

2720528966235

result:

ok single line: '2720528966235'

Test #22:

score: 0
Accepted
time: 63ms
memory: 117900kb

input:

5
73420 141910 732605592177
103634 465909 565581954581
307835 399367 924270688805
190000 225698 627789903790
148282 381965 843272741005

output:

3127938925777

result:

ok single line: '3127938925777'

Test #23:

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

input:

5
316262 448238 61215935197
220146 343713 940110142942
4530 270797 822763137367
375359 489296 910343152529
81496 415552 927124808900

output:

2777578104371

result:

ok single line: '2777578104371'

Test #24:

score: 0
Accepted
time: 48ms
memory: 116812kb

input:

5
229810 288096 398389097524
110567 218685 300955078248
428034 489264 580345694780
409137 412990 842837841485
71766 281403 926629462334

output:

3049157174371

result:

ok single line: '3049157174371'

Test #25:

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

input:

5
35757 120821 854716497767
173715 292576 546105254104
127803 161583 393694430935
33157 242449 741821067538
222138 258578 339604891963

output:

2536337250344

result:

ok single line: '2536337250344'

Test #26:

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

input:

5
314600 337292 456007989175
396576 422354 54971927975
317384 363858 153054470973
137871 266332 4403667486
141051 309491 783064490053

output:

1451502545662

result:

ok single line: '1451502545662'

Test #27:

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

input:

5
27450 399199 671365990301
340061 467799 244391514596
162035 188726 190125474384
98212 275723 595556355629
22282 427392 617664442201

output:

1511313860526

result:

ok single line: '1511313860526'

Test #28:

score: 0
Accepted
time: 48ms
memory: 115412kb

input:

5
166586 464221 722189538518
318177 428302 84811153755
319652 419406 166704276767
17333 77479 322050015646
35148 475349 451797081715

output:

1496036635879

result:

ok single line: '1496036635879'

Test #29:

score: 0
Accepted
time: 58ms
memory: 116976kb

input:

5
349993 402585 202948293812
10826 65389 659792588612
177445 484653 583800803507
2153 124458 934886389069
68356 471750 725691983391

output:

2904171764579

result:

ok single line: '2904171764579'

Test #30:

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

input:

5
329180 377771 719795822738
78518 257595 56915850868
119137 158242 560200520735
236801 282977 439479200704
5061 112589 429084234274

output:

2205475629319

result:

ok single line: '2205475629319'

Test #31:

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

input:

20
8626 394252 916000580598
129635 241322 510930004026
209464 486216 732530235325
102626 190878 133745103110
33992 190970 149884808397
30885 164589 81764399125
43406 294771 948750599279
293469 306586 296531730558
30375 375581 931933695062
136200 499840 436169449921
266668 409113 577333111235
26838 1...

output:

2568053627612

result:

ok single line: '2568053627612'

Test #32:

score: 0
Accepted
time: 55ms
memory: 117156kb

input:

20
171406 306883 871658357274
242449 348182 640524752021
307425 332662 822363982003
21185 26842 192463880855
278653 437920 142195400456
21693 359311 84856990460
269202 412899 366373020378
327938 358364 920331178935
118322 289379 681508219796
32579 218530 382792973914
278710 483597 745747603411
17858...

output:

5018830153297

result:

ok single line: '5018830153297'

Test #33:

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

input:

20
453718 458672 190969231244
133674 293841 597019490148
137120 221210 844326135441
43046 256985 546769929768
38386 346399 921592481996
60850 201528 531911255626
94350 172656 821619089376
49788 129813 736450069748
164266 391003 160570076488
18072 417288 366427880100
219346 384371 563136379759
11440 ...

output:

5237352532657

result:

ok single line: '5237352532657'

Test #34:

score: 0
Accepted
time: 55ms
memory: 117380kb

input:

20
26810 452097 167051430298
165505 199499 982856570714
383317 419141 174136708459
132129 395202 472249315872
191766 382604 69857670830
18991 408912 688934683899
73460 151539 636125459560
1543 325128 795451916757
59962 216010 792075561336
7429 36713 902698040119
3285 44936 950376016901
217844 447447...

output:

5019394129533

result:

ok single line: '5019394129533'

Test #35:

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

input:

20
370987 450054 641049494417
23667 442883 504410057121
182369 297340 13142512206
145671 250037 122121401056
308688 407608 890109806874
368333 384818 339784726677
192852 224097 168668887241
178330 393715 536740677062
154597 450910 211379310522
140768 376272 825384317534
98645 329838 520407819494
247...

output:

3765645551063

result:

ok single line: '3765645551063'

Test #36:

score: 0
Accepted
time: 48ms
memory: 117156kb

input:

20
166229 252962 356485927771
253258 322645 255296863042
151907 354056 558639891577
182665 382580 976464663804
46716 404697 188713362424
86651 187523 815446587
51527 395246 170215144764
118337 216755 281205655786
184252 312171 11976722478
152513 380757 721263185667
336720 481859 343427411506
90380 3...

output:

4089884400257

result:

ok single line: '4089884400257'

Test #37:

score: 0
Accepted
time: 55ms
memory: 115624kb

input:

20
56957 192831 600288944252
175941 187232 927029085941
59023 402134 995896438671
211055 259956 128805383273
75535 281564 521231824045
122522 158281 895086381455
28468 289571 622024396403
334582 493249 577647256297
258376 347906 289949591324
329079 444224 275776591500
13894 86868 884583688394
101694...

output:

5009412832928

result:

ok single line: '5009412832928'

Test #38:

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

input:

20
199137 417159 670723396984
58018 318809 86085738565
296082 325086 947124447427
19212 161872 368143507591
136920 328369 572652431945
154198 420087 29281570634
213635 339438 973587705490
446937 495538 687715752082
158164 287363 243216407886
186319 348287 65746098179
20664 268226 557888482887
78174 ...

output:

3707897901986

result:

ok single line: '3707897901986'

Test #39:

score: 0
Accepted
time: 56ms
memory: 114748kb

input:

20
71209 306643 120393906628
89367 365307 645071610340
446213 465696 285972993436
132782 494746 975832952014
28520 316046 695868138440
277879 381480 898981944934
29904 446676 578963560370
40223 378162 253142240003
69336 458629 14855300366
169286 491186 692829713071
208684 213748 895203706729
301308 ...

output:

3559241364748

result:

ok single line: '3559241364748'

Test #40:

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

input:

20
56107 106597 6708178744
224977 376174 365210213649
163785 493200 583162978514
86284 184681 31832151499
45121 352822 759777438390
92455 112363 889650674975
306350 454971 335049421636
252228 399384 290771582847
287433 413282 220385080030
22860 312327 144147505649
409070 460349 657277508558
373785 4...

output:

4600865773207

result:

ok single line: '4600865773207'

Test #41:

score: 0
Accepted
time: 56ms
memory: 119452kb

input:

50
246653 287997 831450176866
327716 331599 588797554513
205496 469538 895281101872
127657 336454 57660155358
313345 404866 448282293160
422334 443597 25503878411
22413 97911 161421059593
91232 369934 128505279546
235595 243044 3070385701
94770 122848 109135756268
214967 370906 893572670380
190547 2...

output:

9089409512687

result:

ok single line: '9089409512687'

Test #42:

score: 0
Accepted
time: 55ms
memory: 117884kb

input:

50
74198 241963 996934376437
258389 399850 502729435563
11033 296463 126682004270
56681 254168 487289027197
149849 380026 643851527757
432230 493420 795580264592
185347 188393 822875055835
253963 434470 304056383130
94786 335562 69162122282
90901 450934 289708013555
115517 374367 588138247913
74640 ...

output:

8874704589743

result:

ok single line: '8874704589743'

Test #43:

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

input:

50
176740 267708 662080823093
65674 267412 956293461397
425024 464664 86100339258
316288 389664 638112728258
231892 469576 731623350066
315780 461892 7562034362
133771 461981 565720721885
131853 291397 55659620132
82485 87305 315749582628
254619 345536 791776094799
77898 79105 119714085720
31140 119...

output:

5084041762056

result:

ok single line: '5084041762056'

Test #44:

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

input:

50
160272 372561 786609484401
210604 394987 338154757008
25932 373772 496811228520
296387 406005 740068377085
34006 43552 568068832711
51755 204208 309250254188
205250 463861 514515804320
20880 479570 120252773205
215827 430786 240813950323
4760 259520 760379524800
175802 370660 642545245305
202190 ...

output:

6947935992210

result:

ok single line: '6947935992210'

Test #45:

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

input:

50
394836 463467 565589450872
7593 162873 43665815569
203849 460659 950077235097
294545 455770 734299920256
255530 496341 836699804053
100977 367618 924639559170
234921 338016 747689071826
46373 110704 993646748214
305809 403654 375530483348
51093 347144 657342477
23311 314032 766129492305
15966 252...

output:

7961884646969

result:

ok single line: '7961884646969'

Test #46:

score: 0
Accepted
time: 56ms
memory: 116132kb

input:

50
100474 486957 587569957431
74807 303747 167792492958
134303 245275 355610120522
259414 451664 960153978023
112287 397011 97544918495
265315 383672 308467988635
145018 335093 861826527502
174337 488021 819160301048
135167 412094 590587553449
311457 408925 714576751021
234321 317805 459830000715
34...

output:

7152227798123

result:

ok single line: '7152227798123'

Test #47:

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

input:

50
124565 447215 628463289051
148570 168045 251971461875
93938 487323 909183188643
336094 498179 635812838535
199948 270571 513295994255
12459 159735 845663612721
185328 353670 572660387392
234969 304636 173340418561
350899 433405 872575826317
436257 496034 8652333001
21017 227939 99096947684
228806...

output:

8489575528746

result:

ok single line: '8489575528746'

Test #48:

score: 0
Accepted
time: 42ms
memory: 118256kb

input:

50
127893 422059 436057483708
309103 376447 371387101470
120134 482948 703747824897
183112 357459 610372493669
279050 289346 4257602068
188979 433619 212771254075
85318 374079 340557813982
483839 485043 366940353459
412967 489234 544124913796
27576 51214 104221158424
69016 172413 79900700076
195937 ...

output:

8074484561769

result:

ok single line: '8074484561769'

Test #49:

score: 0
Accepted
time: 56ms
memory: 117840kb

input:

50
112101 125507 657121910729
37498 223844 149131215895
179569 313807 120868718912
20835 294107 381393580934
98880 238708 963680254923
207128 460664 340173617624
127293 187150 903242195032
207735 379286 834583768995
192608 203609 218297718626
122546 284813 661351586870
223224 240087 381846921540
480...

output:

8288754717568

result:

ok single line: '8288754717568'

Test #50:

score: 0
Accepted
time: 55ms
memory: 115652kb

input:

50
322069 470087 9387605952
217236 424630 854491588003
213484 217123 245612868620
139132 169165 410828820133
189033 329286 334265492462
187056 226309 956949023513
324417 389064 266513115761
231957 293471 821403676169
129189 176086 718230633245
70110 424448 511230549513
247225 486082 623824392815
496...

output:

7780764971909

result:

ok single line: '7780764971909'

Test #51:

score: 0
Accepted
time: 57ms
memory: 116604kb

input:

200
72743 410316 104252300991
355754 367938 125696703731
352536 358232 944468273515
130332 203577 354370716323
176008 365874 262303921007
88756 376651 239315188946
113254 174597 453127493954
32962 251389 663688323093
359105 461899 725441122060
117834 453923 125709746909
350940 435493 341369245050
29...

output:

15079136104722

result:

ok single line: '15079136104722'

Test #52:

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

input:

200
336801 383415 260690423811
226571 330524 515041779756
189215 485491 853610526251
383713 425287 497105022595
145226 496849 495722902212
284643 286863 776254874978
142402 250636 905561094851
12506 229732 999573630169
231417 385441 296040723629
316994 343281 390791940719
144625 430403 560616370432
...

output:

16670385356237

result:

ok single line: '16670385356237'

Test #53:

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

input:

200
48773 49378 325242603704
252252 432513 46532054274
86665 270602 577526780327
279392 311806 772694912932
86997 259628 740482610359
73708 324285 943482711010
109266 334842 586205572008
37255 376355 460585024496
239984 333100 79176745976
286574 375129 659392543500
113716 329795 454479396684
171068 ...

output:

13205779865688

result:

ok single line: '13205779865688'

Test #54:

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

input:

200
42337 449995 835586332824
287277 447731 942219419487
100902 208744 915494898578
28843 369114 864145510614
77105 104039 185353975385
177915 290639 883976151261
52976 175706 48198626830
351120 405182 777973480184
142374 412553 916999744299
92332 230737 201041595959
265816 278318 363563484592
48385...

output:

14825696241985

result:

ok single line: '14825696241985'

Test #55:

score: 0
Accepted
time: 63ms
memory: 117700kb

input:

200
123928 478858 827077184798
192455 337653 971364009812
135946 320121 133357265394
80351 340278 399757543205
225794 245684 135657104202
104091 432293 335030771931
28122 150082 406983993188
315655 423114 51777036342
86132 307008 516627751699
34331 356802 423154028368
245640 450054 266747772278
1528...

output:

17323260738235

result:

ok single line: '17323260738235'

Test #56:

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

input:

200
40536 337633 247881385179
336944 458348 609275578890
262636 492388 722452231538
13787 436982 588838578718
273997 302306 667772698958
290853 428449 664600367412
191954 271847 322097420751
120367 482681 464986372443
293426 423305 348379528591
56702 281489 598742836962
388071 396823 554378303944
18...

output:

17768598849238

result:

ok single line: '17768598849238'

Test #57:

score: 0
Accepted
time: 55ms
memory: 114860kb

input:

200
34599 448930 424168000448
378548 457737 47238044832
65535 329121 129521639145
99534 240248 277901268212
74253 205367 849633973734
33062 193619 247851494294
23201 460395 615763821262
53283 436520 617363460715
47083 156642 165773394282
99526 415808 191988026679
272852 457749 682002721578
262481 39...

output:

16507204418300

result:

ok single line: '16507204418300'

Test #58:

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

input:

200
208564 348537 581631848892
54815 208487 17879180836
311980 338548 400214076287
194572 345150 61768390465
85975 87869 569977108009
259334 396624 584409867911
405303 466837 365227540207
209776 308490 242419606875
128114 427600 41638272261
251913 299300 529053086995
156096 393625 136895360559
47988...

output:

14309025643270

result:

ok single line: '14309025643270'

Test #59:

score: 0
Accepted
time: 63ms
memory: 114760kb

input:

200
20619 39875 974934733172
362685 467589 443954346160
131649 469251 176968998791
51687 484317 787162048874
400721 439317 911744071303
355896 473338 51951386169
433377 471162 960764936994
8213 485852 37959333005
406232 463772 931204737755
181728 490556 999682314672
140395 323367 133218999705
10418 ...

output:

14519727306146

result:

ok single line: '14519727306146'

Test #60:

score: 0
Accepted
time: 57ms
memory: 116600kb

input:

200
86415 225832 807870457613
140374 283463 14956625045
148881 465122 759599721997
59784 299524 585607704471
51420 451792 851741596266
160231 187543 859611233432
194151 449256 134860193489
54026 442380 360903158191
211970 292318 478203490216
125493 478515 371441340400
330426 449790 77916939066
33569...

output:

16834975149166

result:

ok single line: '16834975149166'

Test #61:

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

input:

1000
95644 183861 844531238026
109235 326392 396004897727
35895 41490 132475180032
224278 495212 750881068341
352312 416348 26317576678
271005 421983 474427166777
382058 448625 184740228658
2156 256895 710650942540
333758 353062 552351903823
236801 329297 113361236738
11279 206925 458275626696
92200...

output:

40510883325154

result:

ok single line: '40510883325154'

Test #62:

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

input:

1000
216107 366493 312836701746
215709 482764 326744897436
33176 206305 156052923733
44599 242096 189693159908
420329 465997 904319518874
205689 279111 122043625633
70220 182909 547363081772
72692 234823 184354851764
284789 473918 819166728857
422814 461879 917718817506
75573 361402 652453750983
434...

output:

36097902120347

result:

ok single line: '36097902120347'

Test #63:

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

input:

1000
72028 451851 37106061812
394125 487213 696620970081
187091 420649 444778583384
343851 382930 466893473765
63869 218377 919354519648
174173 245049 978626959842
52116 296011 414740839847
387250 442933 23939801349
110054 331180 641212464655
270226 304021 662351611752
184511 437204 59240785016
3595...

output:

35979193554661

result:

ok single line: '35979193554661'

Test #64:

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

input:

1000
75480 263441 870712127087
172012 401079 310967401984
39037 412506 893094172724
122194 464937 239705540973
25987 456395 856107800340
3773 77944 470300524054
160713 353129 665899591003
317791 381122 337536616894
50705 174734 568984450980
107548 487881 509000263567
220609 406053 218953406633
65094...

output:

34643361917179

result:

ok single line: '34643361917179'

Test #65:

score: 0
Accepted
time: 73ms
memory: 117396kb

input:

1000
178922 455270 20560941386
67207 290144 684990866712
76228 138796 760951725791
224565 420791 541229763567
93074 420744 507347487307
320009 395904 666604144299
336409 441618 804942002464
201617 361724 189925084774
20968 370591 959613099698
88678 294125 882877781992
92798 250939 711888935154
36621...

output:

34423428201661

result:

ok single line: '34423428201661'

Test #66:

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

input:

1000
353140 388688 233860518195
198754 268991 983914224040
108606 395793 295711785742
111566 129211 233609975034
112390 164997 983590015348
150391 404774 978625044288
271043 379085 79535938340
297936 433206 967031582677
224258 366726 287835794566
407828 414035 618927909468
371362 470105 38888295038
...

output:

36931343646888

result:

ok single line: '36931343646888'

Test #67:

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

input:

1000
56071 206942 646538362256
299911 306395 103659469334
35731 234168 44509199769
114824 204421 211337001728
148267 261858 269713041123
16882 145071 224938621327
114104 375572 509947123634
37039 308792 605775000694
262354 269321 350723909010
23324 121467 678512813318
63250 196932 773229088718
16016...

output:

36757652891084

result:

ok single line: '36757652891084'

Test #68:

score: 0
Accepted
time: 76ms
memory: 115744kb

input:

1000
83222 96943 488054682234
148904 307324 76693023551
73499 233355 795900140239
104585 413996 555046457575
156579 422192 967091874160
305563 432428 810061112035
104104 156413 595489146555
283359 455633 990436613803
351757 356717 367872791265
168676 322445 205760635185
228322 302720 235156277753
21...

output:

33157457971827

result:

ok single line: '33157457971827'

Test #69:

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

input:

1000
346796 487064 58727733244
174505 194855 471179991031
126739 163840 914901897163
243550 294280 185338049101
441100 471411 675009072599
18824 359966 24478027538
143118 268943 331855746710
15592 131882 565487500625
206280 206445 523772910322
11157 119117 503539513464
9214 472532 874054222836
19728...

output:

36236433478238

result:

ok single line: '36236433478238'

Test #70:

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

input:

1000
235960 310715 501399849105
265292 283647 350572820431
86721 309436 314710681733
306499 410240 471625087553
15617 51417 779840227143
20928 253741 443603307439
138847 423489 340385799790
69223 280407 261712300178
219301 298436 363485190625
194113 272472 367761412891
13074 121767 719197378284
1210...

output:

39249622887744

result:

ok single line: '39249622887744'

Test #71:

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

input:

5000
219718 260838 467342096077
101020 274542 944771588833
96036 414347 650265447987
241829 359577 602350327205
45467 118614 107470176635
48116 497329 547861877209
356783 467516 192300205965
132105 308579 220975573580
255974 308380 936334082565
417735 457174 937850613316
190167 400699 854665618480
1...

output:

84064063136708

result:

ok single line: '84064063136708'

Test #72:

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

input:

5000
22656 438330 920911710842
111746 444151 95893359337
75790 395718 963988411270
355545 461031 82719541341
17840 296443 264272333342
98214 353021 915863041857
16822 170807 61148970477
68858 437735 872796439532
242504 474192 187941958321
18309 250859 946255860731
90745 258238 689846379453
268507 45...

output:

82528317664673

result:

ok single line: '82528317664673'

Test #73:

score: 0
Accepted
time: 95ms
memory: 119552kb

input:

5000
131327 330527 215277910497
247785 376595 581485061727
146660 333457 808419257398
303150 370512 278932628486
219503 293721 926407597231
148765 465063 255432993749
75879 385909 587933733258
401375 457474 87415778040
43154 358995 171698514773
286682 357435 194296340802
147927 437601 213983196583
4...

output:

79157578658735

result:

ok single line: '79157578658735'

Test #74:

score: 0
Accepted
time: 92ms
memory: 119584kb

input:

5000
85816 482074 651132396826
146143 392184 500777740507
168742 253101 488885514032
319530 498170 584756106894
132637 331059 283449599001
94525 355238 269990068267
90818 115912 351044591994
187253 217465 465358627793
227098 235819 935950634663
39815 226033 596631031885
407082 437896 120433095485
67...

output:

83170329162806

result:

ok single line: '83170329162806'

Test #75:

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

input:

5000
307156 477167 824058333610
310868 382815 836647407285
362 266508 780561326972
202392 247023 188689402028
17369 166520 577882533689
226177 420247 888318511932
92011 98922 121872623747
49238 172814 511177841145
64482 467476 911422648076
21437 82690 86559021534
15436 151741 434793476876
234655 309...

output:

76876968255551

result:

ok single line: '76876968255551'

Test #76:

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

input:

5000
216811 478100 825869274155
141481 161464 239935978443
136394 156272 931510897771
78069 209478 528002689047
256975 357610 938870205750
411576 444060 42356854676
154425 334229 844708630462
235622 289145 920641935366
150455 446381 359804531373
68974 473731 531460152595
216246 331646 999926837680
8...

output:

79872601294801

result:

ok single line: '79872601294801'

Test #77:

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

input:

5000
241394 302530 625975929171
39229 87651 561880535474
298587 366622 884069314622
108560 253034 314510861780
144226 150216 941571490088
378322 447124 597005145627
22288 189921 138915498844
286791 480394 836447179942
295734 456980 384763031632
364024 434136 169747424187
9460 65312 604154001947
1879...

output:

82327379450959

result:

ok single line: '82327379450959'

Test #78:

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

input:

5000
167938 330795 854679389294
78919 469920 306183701763
288990 337949 491769464554
165180 444308 55267853309
135751 344721 793865233117
76404 231142 231537635864
16752 63693 324854004134
151777 495019 369640192745
260865 396516 559516090105
262428 343376 888869492439
185989 246855 646141987674
170...

output:

78204108288207

result:

ok single line: '78204108288207'

Test #79:

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

input:

5000
258213 302614 903493484422
243198 468766 245795968503
227247 239089 244287927681
14830 123156 762201475905
303335 427233 151507423604
196791 260071 637267293205
260577 341888 33121620390
80481 344721 97589759257
371114 437332 132156589233
171599 352989 944964776818
155187 269372 264121160014
10...

output:

82547808000516

result:

ok single line: '82547808000516'

Test #80:

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

input:

5000
172807 310228 524989856201
262097 323842 808542994067
160490 425334 942201359128
147835 377557 962392629527
349014 395980 450910321915
95328 157554 218203593217
6336 41419 22243924413
383373 461500 425798706526
266744 287711 32996406800
80326 198184 964055462650
262716 424475 277790286960
96414...

output:

79681091310675

result:

ok single line: '79681091310675'

Test #81:

score: 0
Accepted
time: 127ms
memory: 122264kb

input:

20000
90701 467811 411352666387
204090 480688 666664069718
43117 377654 670804155719
56704 151816 768467164504
22842 361444 410843003843
229509 291946 280364432769
60054 137049 211211254190
307592 368192 993458401776
415015 421427 818427510498
90334 302621 496954159057
334058 440501 561736616128
257...

output:

160845762289724

result:

ok single line: '160845762289724'

Test #82:

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

input:

20000
331852 333552 779267543446
81000 376553 121016789737
4806 333003 213885528596
397581 402742 297455871399
150853 174747 832906359973
285786 310519 911410437509
164765 369363 691381948666
274068 283903 331157962057
100818 363293 243330340968
308405 485851 962935395512
126770 485631 825958600063
...

output:

162000890919174

result:

ok single line: '162000890919174'

Test #83:

score: 0
Accepted
time: 126ms
memory: 121428kb

input:

20000
162236 340502 760478346323
58449 244403 471479656505
162470 209384 201031622841
224942 457449 793541127382
206243 495755 349085080002
149631 495211 431660417589
95120 112461 32436016406
90909 168769 766463607761
153881 377313 989700947463
79526 329896 207567442270
36266 126642 813051180029
188...

output:

162023859701403

result:

ok single line: '162023859701403'

Test #84:

score: 0
Accepted
time: 119ms
memory: 121748kb

input:

20000
196840 231694 949987083218
91490 154293 167526738243
173944 200898 461306156229
208400 475519 596254345160
101090 459910 127756171787
27218 71611 128784794277
44739 282463 982093983467
104428 218863 607676128419
48288 194480 67845834125
385014 477358 635628967031
367413 386270 630389175613
159...

output:

160025098474315

result:

ok single line: '160025098474315'

Test #85:

score: 0
Accepted
time: 125ms
memory: 121308kb

input:

20000
359094 359656 565233405237
97105 167108 975429061304
257252 430129 175576521395
332074 369866 688230948386
122033 428172 810546491965
295305 367462 164635883074
402442 416345 296384517179
263135 395001 565841325336
209311 437027 727854894322
150828 275730 816961544685
80895 149582 832218347980...

output:

167174591388647

result:

ok single line: '167174591388647'

Test #86:

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

input:

40000
97396 324067 271771465706
214453 288306 353435325306
321864 426257 990722747080
165093 425730 286437288579
70483 70919 296221137301
41149 356417 166621212120
120833 429957 403302150686
51458 124224 898295719750
306065 330500 560197922164
264156 369124 428092006664
236564 290375 713120657252
13...

output:

232055876245984

result:

ok single line: '232055876245984'

Test #87:

score: 0
Accepted
time: 164ms
memory: 126812kb

input:

40000
397552 446722 445567942933
186531 440685 564240751084
236548 252469 643392526404
91185 293380 694733548899
12540 421639 66290321782
283300 304727 555659196792
134935 191338 629033017774
19909 357200 564338469598
14982 87616 106562333415
28281 301618 999564911432
331462 348234 328295519856
3298...

output:

233743028321438

result:

ok single line: '233743028321438'

Test #88:

score: 0
Accepted
time: 170ms
memory: 125136kb

input:

40000
238277 405385 19756530884
325192 338972 825779897822
87505 145111 450096988773
295238 301636 456749856024
344726 396638 130465387665
132978 410998 747586283335
27823 448455 294769638752
143334 361332 629751058231
206873 285541 921131163008
93449 162242 756529608767
27745 389658 744911058357
15...

output:

236377049870178

result:

ok single line: '236377049870178'

Test #89:

score: 0
Accepted
time: 175ms
memory: 125604kb

input:

40000
21966 457150 295417838599
71972 191711 817832115819
179655 375945 693900003741
182831 318671 10832901160
170477 462958 753356694719
319362 480643 77155000185
193670 421088 867287317960
203174 408085 188005913432
173129 247498 661311646807
116930 312854 744801275860
219385 280651 657701624264
2...

output:

230126119414256

result:

ok single line: '230126119414256'

Test #90:

score: 0
Accepted
time: 151ms
memory: 126672kb

input:

40000
80653 83066 967138299666
331676 403833 80345311385
218665 438563 774717802598
222139 447070 444508729377
52585 401892 261440991659
43275 200137 631607415061
203572 272260 266513314220
79990 465835 746689940500
228412 312781 85216972840
106751 398347 944552437229
22893 24510 462534340483
206532...

output:

225862244194989

result:

ok single line: '225862244194989'

Test #91:

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

input:

40000
328855 477908 551722704186
31439 185288 361816152288
119205 316920 552202537063
389271 476519 60054492182
289998 475362 849498215892
22341 329343 436460203852
158970 220049 77523482424
159523 297508 600791316034
152793 156212 304260699718
212110 479095 178053532679
178882 409536 138377042905
1...

output:

231473994270680

result:

ok single line: '231473994270680'

Test #92:

score: 0
Accepted
time: 168ms
memory: 126848kb

input:

40000
80966 464033 37552200375
266620 352183 420264262074
41739 465489 614125544568
384472 398781 683294226465
31080 186312 692144095868
447452 468614 178442597146
396395 404990 257429774369
129180 383857 251375961996
426425 433887 428184023283
54563 314487 583632296575
383193 432228 18383542304
142...

output:

222950941301674

result:

ok single line: '222950941301674'

Test #93:

score: 0
Accepted
time: 159ms
memory: 126688kb

input:

40000
461433 495900 338354495874
245526 401283 456669168852
224143 377705 102790527150
53003 493315 369570577896
114842 296674 523826192652
19451 474054 832144431123
348633 430732 730805234409
114967 419230 866617516455
368916 424568 259019881975
61036 226291 260546631939
168351 327346 631361113655
...

output:

225882629397737

result:

ok single line: '225882629397737'

Test #94:

score: 0
Accepted
time: 155ms
memory: 127232kb

input:

40000
88782 165407 77194762173
172160 430121 325869160709
286245 434372 494583291145
156645 413385 162362235881
131048 480154 63700981315
75925 397291 388520909126
376062 480872 317702224541
87644 350163 490626685166
112640 303647 908239051931
31944 309885 755014610803
314901 467495 861173385331
869...

output:

229110985318229

result:

ok single line: '229110985318229'

Test #95:

score: 0
Accepted
time: 161ms
memory: 125156kb

input:

40000
287237 485116 284783898740
396868 458302 862327319561
19088 322359 368453517420
20007 376995 463087734610
137483 232187 523779637297
358226 432330 258190232504
75734 197784 134800764122
146591 297483 939803374573
353598 446937 674669430854
290731 393198 399329038223
277944 467074 277489104866
...

output:

227870609919504

result:

ok single line: '227870609919504'

Test #96:

score: 0
Accepted
time: 166ms
memory: 124928kb

input:

40000
84166 422039 536044896300
388565 472271 649477883825
321680 451367 907052920159
242787 306267 902752377350
165039 293871 877179791664
172113 238183 988419985277
63670 431540 93864044855
203987 373853 64817285485
97086 104574 740187126231
175309 286705 62102285186
171620 186427 225601998073
768...

output:

238347795472616

result:

ok single line: '238347795472616'

Test #97:

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

input:

40000
296796 371447 134367578946
353107 449150 773044057847
138201 294053 14305334229
36652 192017 665329661757
69961 408986 750283160759
62544 307314 445562768573
171387 319897 827420591783
129652 451995 286337655106
112674 254770 605275948322
61691 286634 915007633721
181661 219732 240895891911
35...

output:

230069261817564

result:

ok single line: '230069261817564'

Test #98:

score: 0
Accepted
time: 161ms
memory: 126552kb

input:

40000
134391 347284 86917155761
32201 66975 18886572134
337673 403525 944706194062
264409 348638 244260291784
111145 498013 342688859677
113824 143254 270830149459
150883 314309 844377431719
290155 315229 180639304365
295572 358232 113051573131
40815 257365 813858340965
216947 252452 625534369626
11...

output:

223407701437838

result:

ok single line: '223407701437838'

Test #99:

score: 0
Accepted
time: 172ms
memory: 126300kb

input:

40000
157011 423541 924388728407
109208 154085 876756781439
359788 498199 69997122745
257784 365036 300646444701
159288 351854 630061919216
181749 357649 645589823048
166799 215696 634861360238
7987 487112 855094625899
128336 281938 51221219968
202475 373281 617128511226
57519 409549 25431160118
729...

output:

235659101291427

result:

ok single line: '235659101291427'

Test #100:

score: 0
Accepted
time: 159ms
memory: 126720kb

input:

40000
326225 332669 855129902829
287353 379101 264184671832
185635 472394 832360978319
57579 213368 58356486857
98784 403198 708721131442
123802 342928 814055047238
9105 50165 795660944983
51280 390447 968544228739
179591 272373 860610890979
105168 400315 157943880154
40155 344939 591525475553
20302...

output:

236467983475024

result:

ok single line: '236467983475024'

Test #101:

score: 0
Accepted
time: 164ms
memory: 126080kb

input:

40000
137820 467351 134818349298
77167 273439 847297528925
37089 241397 134457388888
120504 320991 534129951662
355834 433479 272590618848
230323 260008 955954329994
303520 419052 340440340035
124479 152448 300559897834
9157 362312 811131178551
39328 85255 97831330215
82831 150043 833788116510
77214...

output:

230216971636302

result:

ok single line: '230216971636302'

Test #102:

score: 0
Accepted
time: 148ms
memory: 125892kb

input:

40000
277934 329147 24824510716
125867 220695 125647784118
72295 148105 59057017932
180750 427935 977025364423
139567 391454 773280682734
89994 475779 195706405488
195821 290290 553984221186
49516 210225 791102456805
371825 483042 425516416737
67592 262170 466809293109
179564 434216 760624240402
233...

output:

213160502685519

result:

ok single line: '213160502685519'

Test #103:

score: 0
Accepted
time: 159ms
memory: 126012kb

input:

40000
468684 491179 962277932103
26317 65397 104550646325
115540 474026 908176857022
205983 291135 274359314347
40923 426230 322047884960
139222 478140 637092065102
170544 203204 256705872138
308207 348657 686443900788
70815 193664 648769368292
5016 312192 169608652360
219117 449198 716404804137
287...

output:

219882251336186

result:

ok single line: '219882251336186'

Test #104:

score: 0
Accepted
time: 160ms
memory: 127132kb

input:

40000
11968 177603 681672241085
434031 459809 380483759907
107648 439964 360868537930
155345 257788 721005140977
11449 14148 417715267389
119969 212856 955533008820
48705 402421 787566523807
84162 208156 20649387070
12932 77246 113665265071
32301 452643 385540375487
205666 254107 802368529646
202595...

output:

223983954758492

result:

ok single line: '223983954758492'

Test #105:

score: 0
Accepted
time: 153ms
memory: 126952kb

input:

40000
161955 434954 81344510457
274100 352217 1680547970
121172 240861 504833994972
230673 495759 543544990343
246266 352234 512113763341
72946 459469 759594944691
94840 491805 193142151484
218439 407251 196380787834
84977 255679 291755444607
145216 384020 896055503189
65104 229259 832008933434
1256...

output:

219904448105014

result:

ok single line: '219904448105014'

Test #106:

score: 0
Accepted
time: 153ms
memory: 126584kb

input:

40000
233934 425828 792549326009
75017 332248 401143251615
180561 434469 478211684576
222357 300462 213486163122
102064 174085 428896732356
279923 441777 158859561676
62845 108095 336306851816
70936 155351 168652236521
54557 421481 202480605547
212699 292008 320751783938
334468 418674 910782420438
1...

output:

230454447933620

result:

ok single line: '230454447933620'

Test #107:

score: 0
Accepted
time: 156ms
memory: 125064kb

input:

40000
120598 297260 220169120654
78883 228867 298481086605
278695 282079 927413697147
246161 380200 117689240165
81548 482583 331397831336
132040 375418 597248840652
366175 460448 637424644424
267523 393048 420107952718
221454 459847 148887728176
328625 483679 742308251260
296019 417249 361710393746...

output:

233945058686230

result:

ok single line: '233945058686230'

Test #108:

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

input:

40000
118508 309700 414438187629
37259 307185 594628295991
116843 127667 214579002548
338302 349840 61658183481
7362 88089 41548525960
187753 420965 763313329610
192700 275036 543669984450
16514 34437 149650512969
41642 156982 905750067117
177300 465204 775024178599
49162 127894 824914687475
324623 ...

output:

241147060770286

result:

ok single line: '241147060770286'

Test #109:

score: 0
Accepted
time: 152ms
memory: 125136kb

input:

40000
362057 379522 529222105229
52758 151625 453219495121
175708 240480 462517077064
411955 454024 4256259088
263719 320752 592761261594
135164 484608 162075778931
196181 295519 731754605898
128605 135594 830796010108
312716 387270 430315451369
352287 380825 919401550689
404710 464287 881854242759
...

output:

226741137902901

result:

ok single line: '226741137902901'

Test #110:

score: 0
Accepted
time: 151ms
memory: 125024kb

input:

40000
402478 484303 910388800535
174194 372319 148292359494
355698 427097 607264070300
49677 314027 581022716569
62508 322957 444049589001
217600 386545 836164165701
275659 332939 781476951780
287966 392164 526886999650
90570 479632 565624951227
250116 365892 166832859046
194555 377133 154690669563
...

output:

234880129051128

result:

ok single line: '234880129051128'

Test #111:

score: 0
Accepted
time: 155ms
memory: 125908kb

input:

40000
157531 417303 669616476251
38304 471764 638845823489
267366 302027 741893375656
69514 273495 212817009255
253701 290032 534946875652
248570 442713 319605207451
341583 452093 729757108896
265451 393523 24759096743
277109 330348 696245581706
288262 412013 60093882658
279994 397687 489655744308
1...

output:

226297531582479

result:

ok single line: '226297531582479'

Test #112:

score: 0
Accepted
time: 170ms
memory: 126068kb

input:

40000
121777 184181 376090645813
107579 478397 210043749328
25143 107789 161686910966
250161 447510 942985428950
32467 432793 478230470822
83013 216958 104341600655
29827 366212 132043139404
60149 197520 76203832396
33246 238408 585104946710
295115 390860 696470141134
190851 331826 594679024761
2427...

output:

236493445169074

result:

ok single line: '236493445169074'

Test #113:

score: 0
Accepted
time: 168ms
memory: 127332kb

input:

40000
213004 488339 533318499923
11362 188857 192557663942
40686 215501 866746388016
156737 425704 803781929684
106705 254977 870465619472
185667 453319 689383610811
53294 116863 260631687015
200496 476452 593247023306
49168 217682 30385458849
70420 139028 825187177121
66786 448988 476987494812
1105...

output:

236970276957999

result:

ok single line: '236970276957999'

Test #114:

score: 0
Accepted
time: 158ms
memory: 125764kb

input:

40000
133445 281132 499863092813
64258 439740 301698681355
204815 314598 530081826283
84086 324981 315267190988
104225 255554 949810864217
215414 216734 307997139886
448910 450286 10671668257
144803 243900 527106217753
368692 452797 199259623909
121061 463680 93896928478
177451 393925 577898415222
4...

output:

228305659632890

result:

ok single line: '228305659632890'

Test #115:

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

input:

40000
298487 467299 235271135408
226126 396872 967331606219
439803 471493 225480022211
55233 196065 158299618833
40442 404806 339922437188
116534 394942 226682306456
207642 417163 687015450918
82451 139499 186944133905
131207 291472 916007086741
123651 159573 51807669607
210660 397229 288083349299
3...

output:

234485312134689

result:

ok single line: '234485312134689'

Test #116:

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

input:

40000
206662 436772 929459486395
75388 223371 883886802310
166688 394605 202213099476
226760 455215 3190739721
85680 191757 761065135662
42769 369199 96103640708
410627 492351 455964347372
344808 412102 694241343023
388631 440072 295359694874
231839 259531 409976295361
8800 493820 904090154021
25825...

output:

237010531504978

result:

ok single line: '237010531504978'

Test #117:

score: 0
Accepted
time: 146ms
memory: 126212kb

input:

40000
19846 44367 655895736047
325302 408080 714702557772
41450 160974 425747775448
198898 337392 12721825404
167485 228436 509518445060
380548 417883 821697312962
17330 377770 587238195045
4768 175701 676341257235
191781 467828 93051584809
143829 372552 942683152864
982 483086 134662752777
56240 21...

output:

227803391904833

result:

ok single line: '227803391904833'

Test #118:

score: 0
Accepted
time: 162ms
memory: 125904kb

input:

40000
352006 420375 275510600133
241188 296537 206292421234
25962 96036 16148928765
46929 352055 284710774122
299459 373564 388528540043
20839 366847 386355887509
174881 211152 748443361079
186521 461507 650782913399
395931 418120 466771614410
149955 378406 520849233432
69558 108468 353494173635
118...

output:

228117006360525

result:

ok single line: '228117006360525'

Test #119:

score: 0
Accepted
time: 158ms
memory: 127084kb

input:

40000
425478 443875 317246556782
51900 431362 296706259790
230465 452040 99172001726
314446 341960 407649729224
153829 261905 672472063283
336374 446112 795681563996
64578 305452 168094302016
243024 468341 777869476960
33493 192837 466790807962
304451 430501 23064315611
3918 39908 703660395277
34151...

output:

238356848704866

result:

ok single line: '238356848704866'

Test #120:

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

input:

40000
216874 374536 865070666507
303761 366160 848071919667
263788 418806 254967455091
52370 65208 341417992779
213364 390037 744830747400
15527 266293 555735736525
121048 494647 681344569084
11800 318789 976740910060
3231 407516 104309075390
63823 152252 799517553655
98979 458014 435490010981
21562...

output:

218788642964730

result:

ok single line: '218788642964730'

Test #121:

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

input:

40000
170503 348919 860702545375
366577 481695 377158762087
249095 256956 5913416979
243292 489158 279802748100
30994 288674 356617918694
62918 280246 537127646957
114773 317775 250104621655
281749 312807 525511113341
190315 355279 389376263692
26421 65082 137778243251
173315 272317 232255846012
124...

output:

233497037021773

result:

ok single line: '233497037021773'

Test #122:

score: 0
Accepted
time: 158ms
memory: 126464kb

input:

40000
177189 367088 323622822039
67421 67627 708640239906
459917 465706 554301994520
349677 369809 84543496129
18637 93107 333580608218
31118 104084 982664137240
105657 226490 97113347433
41432 352219 369545207132
154594 408418 999112352477
203719 371838 532602731081
204290 216483 982255301780
22645...

output:

234064121783399

result:

ok single line: '234064121783399'

Test #123:

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

input:

40000
201022 390299 499460150598
170267 253886 532358056069
145470 347443 760691046076
84096 275743 876333371021
153013 188629 882671097746
341916 356479 697412988579
32684 326460 984005793857
402221 472041 300837346389
246793 309502 241010790151
14785 159569 21952892497
57757 304553 73558275365
125...

output:

228960995996015

result:

ok single line: '228960995996015'

Test #124:

score: 0
Accepted
time: 168ms
memory: 127068kb

input:

40000
131335 371113 767860509782
132295 195584 715947495764
166041 491040 556220870161
221731 497259 980435970303
63997 372635 646447184924
63947 164864 828126979684
302131 466218 163596289012
241783 262361 724838581369
21030 482476 812175333226
73222 305589 20520469573
28939 257956 787687223205
288...

output:

223340629652538

result:

ok single line: '223340629652538'

Test #125:

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

input:

40000
225549 419858 505582275838
226345 489826 931506546435
24651 328048 707311720722
179641 331075 705664996031
233664 312246 589935411332
210115 391154 924197463818
156459 165039 942076008052
101288 272922 130795195060
10888 392002 24182897471
47187 181341 512104073802
106060 296815 66243705324
24...

output:

230373974421465

result:

ok single line: '230373974421465'

Test #126:

score: 0
Accepted
time: 168ms
memory: 125032kb

input:

40000
20599 217499 810112683245
212414 369389 132340458970
182593 307853 487818270044
469818 495160 130153881516
209120 351342 892417097401
64756 334993 451497877727
23533 37020 513288436931
182849 467840 622532165368
245109 369229 605646959910
2846 419429 589704337891
400237 411175 66145212681
2127...

output:

236503763182623

result:

ok single line: '236503763182623'

Test #127:

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

input:

40000
182157 444352 80707615271
261665 264894 855642541689
142702 333144 536528061530
147982 268703 358232706651
240861 284197 849146500387
373902 471546 429292313053
219838 313493 897872098164
383055 499508 887957516931
450413 476450 84976106645
160594 291354 769056660472
309390 439038 159918204372...

output:

244659800657008

result:

ok single line: '244659800657008'

Test #128:

score: 0
Accepted
time: 159ms
memory: 127656kb

input:

40000
107660 353230 75443230178
147002 495427 308078361091
110504 489072 997146762942
24529 133178 893402277991
98459 417864 59404599889
76516 458770 591500526776
234980 444632 723499573300
135958 238585 218811852968
25885 138091 728637866389
247519 264192 93718072375
3751 117534 251844696800
140565...

output:

226918046304045

result:

ok single line: '226918046304045'

Test #129:

score: 0
Accepted
time: 166ms
memory: 126100kb

input:

40000
304677 443357 504426737568
199124 451512 914280011668
58859 186655 156179593876
336372 444967 680007604842
118663 206711 610633044327
303415 495306 597840729184
82276 274396 906686045647
94336 187665 29224588774
177704 187368 157940068883
242876 482737 252011827091
111067 284097 535903114176
2...

output:

225045206855376

result:

ok single line: '225045206855376'

Test #130:

score: 0
Accepted
time: 174ms
memory: 125652kb

input:

40000
345279 366864 891154230818
292844 315217 947109185629
86653 169977 148989343469
402235 488194 571778646765
97478 351255 580607946335
3721 120014 402328017955
283821 322379 355634597310
76615 456227 144627632068
142669 233635 397090697110
138887 211404 251955938152
40056 89219 401194630999
3067...

output:

227542815414761

result:

ok single line: '227542815414761'

Test #131:

score: 0
Accepted
time: 168ms
memory: 127208kb

input:

40000
103340 220307 303505463114
142570 421434 898284429633
192041 433916 527149721694
23408 54636 326816757183
186102 339078 815683876231
9522 82788 45406003782
363573 466641 627683763219
285806 328616 169411772719
192401 343293 765146905887
38854 130902 867559378036
180661 388408 410992923330
2640...

output:

240539346819017

result:

ok single line: '240539346819017'

Test #132:

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

input:

40000
5616 475372 781234518793
236292 296047 98264961688
143863 402700 552270039866
348554 484614 214675582220
264073 437799 531070348237
81813 248558 556237091528
157321 181762 63686179211
83407 115785 485660153879
371577 383171 822247020848
199783 464700 484712896266
327712 452239 987995792148
197...

output:

228036358996916

result:

ok single line: '228036358996916'

Test #133:

score: 0
Accepted
time: 177ms
memory: 124884kb

input:

40000
235726 387508 743400864590
164480 326209 273737225811
234489 438585 272106624150
9412 145417 591067604202
210012 412659 360484103820
256397 292764 546729405630
206973 387084 234017572244
48041 163611 994562817830
456939 483772 538128860424
237175 240045 403119042793
81511 382643 182894442717
2...

output:

235472797889747

result:

ok single line: '235472797889747'

Test #134:

score: 0
Accepted
time: 158ms
memory: 125836kb

input:

40000
57201 368098 910067888051
68126 475013 159871094624
264892 344816 835043048633
263801 345816 830313513789
339219 491313 127271603689
345092 447616 184463836557
212395 256626 732846212725
83204 315611 138831308733
10276 303081 852231541945
228734 267621 393332237861
117022 123632 920849553924
3...

output:

228272764311065

result:

ok single line: '228272764311065'

Test #135:

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

input:

40000
421277 485931 185113133095
68849 275734 698580945062
174738 285963 359996741526
213191 253823 854679984224
87057 393701 479060158891
56446 203987 116946236737
111761 283274 844697145865
38750 258995 267220283076
262006 266403 528387430368
208908 376724 504705505463
96227 257127 629205438320
45...

output:

237742035794560

result:

ok single line: '237742035794560'

Test #136:

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

input:

40000
165477 247034 965149476612
66319 133738 447940159740
73602 453793 300115061263
100433 325775 444004937249
127779 470511 753013240719
72956 343776 313926992492
77060 306541 229132247213
65952 209453 417805535794
217752 361399 499466123307
210867 380184 640942048186
128948 195546 367940182638
84...

output:

225145117244344

result:

ok single line: '225145117244344'

Test #137:

score: 0
Accepted
time: 151ms
memory: 126108kb

input:

40000
245713 499026 60105959316
1074 177918 89831937449
75217 404052 863145376124
370641 400086 424306278633
89440 192925 340420567535
289639 289923 575404892441
14222 483027 552354054785
32790 95361 274544835089
264502 393374 434114506594
95614 155736 759513771515
138523 345418 61751758989
301993 3...

output:

233753575454642

result:

ok single line: '233753575454642'

Test #138:

score: 0
Accepted
time: 168ms
memory: 125916kb

input:

40000
32118 461265 381186497367
338926 366665 557566660669
277726 392111 938194700229
79678 496715 661666777172
307275 441268 659355733794
148516 231539 965283947034
278435 439346 263276109256
23079 116853 424542270768
121160 288806 879099143263
31333 428664 415876438100
230867 408675 724974580771
1...

output:

227806094399737

result:

ok single line: '227806094399737'

Test #139:

score: 0
Accepted
time: 175ms
memory: 126492kb

input:

40000
21882 140546 141143001386
51383 391342 352640320312
46724 418416 568552258154
13207 416138 699018008428
114307 301726 914209271910
67408 439165 362354794163
241785 314061 485912573257
74378 388890 338754240899
51759 54954 352711334671
76260 124493 429680229474
146171 442815 182363863711
177841...

output:

235414066029957

result:

ok single line: '235414066029957'

Test #140:

score: 0
Accepted
time: 152ms
memory: 126896kb

input:

40000
153765 335451 530390493230
126827 491708 442162223738
220644 244722 470444489439
115786 458122 378009487797
243403 460164 855563017336
335836 473384 499119151441
227669 260346 421695453185
45631 152796 124598949354
349491 393366 711222758004
97789 286698 828790898670
66665 176572 945534408560
...

output:

217559695360592

result:

ok single line: '217559695360592'

Test #141:

score: 0
Accepted
time: 437ms
memory: 153864kb

input:

240777
11210 323305 347369443738
136886 277392 58564776356
299650 396589 297069731203
281464 348488 268465344973
65984 348159 567448510613
294887 386423 623204568389
144405 335010 382252483341
151975 336521 418966151433
20773 427486 816403617734
137309 181254 330462868568
135378 426744 431821798847
...

output:

582773208512476

result:

ok single line: '582773208512476'

Test #142:

score: 0
Accepted
time: 142ms
memory: 125748kb

input:

34423
68846 115057 74352811384
180097 345637 192691606247
21810 76576 647270442159
13068 211942 576013959793
271369 474139 25392159805
20328 440072 887641655564
250787 471882 412214306040
318534 353627 288836743462
248493 278287 649322629536
221492 427970 859782829918
108955 112823 262955129322
1736...

output:

217463225098138

result:

ok single line: '217463225098138'

Test #143:

score: 0
Accepted
time: 195ms
memory: 130012kb

input:

63901
359076 362052 903568828775
168976 341305 813082022609
372747 496477 692232822013
342842 432075 731901813602
43669 327730 341538335037
112828 132025 321776493237
51981 392122 758806160481
87144 337261 253817347356
20105 65224 962375605642
381311 429800 102354344249
151342 437942 769754935335
28...

output:

292754196488962

result:

ok single line: '292754196488962'

Test #144:

score: 0
Accepted
time: 338ms
memory: 145084kb

input:

169500
61688 289753 18605009822
53229 439030 357911214344
76168 334276 85351137277
12834 320263 141214582490
112194 450377 221253612465
241580 441637 540338635122
16582 379952 244587841962
270426 428015 321693481203
95720 137363 509227544103
426025 437004 178022144041
73455 493337 471886490698
13213...

output:

489461670796185

result:

ok single line: '489461670796185'

Test #145:

score: 0
Accepted
time: 440ms
memory: 152164kb

input:

238794
225520 313442 232795039498
51695 68206 139652964753
241782 432716 693715152483
133323 374116 767705193640
158840 231263 474763572644
366799 414469 645462283844
34796 331106 486929876143
258742 497421 154069678872
111888 337786 844073674926
280464 421994 30598182611
322327 372722 788067754919
...

output:

563175576175922

result:

ok single line: '563175576175922'

Test #146:

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

input:

46599
37763 123947 523732189174
98965 145786 247251935134
57848 176901 889249647701
66174 364434 500272125367
92697 497130 931501419545
278756 497603 698324369352
445452 464694 230180187197
166657 399843 548371073133
212208 484237 537083718350
166671 223129 679239789537
45525 123732 685668038883
282...

output:

255564691327039

result:

ok single line: '255564691327039'

Test #147:

score: 0
Accepted
time: 213ms
memory: 131684kb

input:

71857
218346 440169 351926127475
46018 358065 434429705367
128691 146773 232964446523
391059 392959 409302960884
234979 367835 832873750032
216663 472397 857476595384
337489 413628 646584678422
178989 295496 891424266179
85879 371085 99958655380
161942 241699 973398572691
207428 336897 658875102340
...

output:

310976132618507

result:

ok single line: '310976132618507'

Test #148:

score: 0
Accepted
time: 440ms
memory: 151692kb

input:

226026
231918 462989 538765075677
206131 374004 628632390623
10556 379643 331206909996
330507 348259 815070769384
97245 115786 795570444534
104435 417444 823484906847
242419 485307 125021482892
43213 210810 720775741596
47078 277437 223563933172
158361 192637 450743605219
38868 86022 684737345088
14...

output:

548693920663685

result:

ok single line: '548693920663685'

Test #149:

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

input:

85846
165122 337724 55850211933
133779 415732 269751196724
144038 435593 724320667210
176815 194732 105310742731
201766 488376 883561329965
247896 330786 443582729522
118231 411897 339624674481
91336 152271 539316189392
117736 137347 393061979628
174368 356084 296302603838
163883 303014 97574673154
...

output:

334458779013001

result:

ok single line: '334458779013001'

Test #150:

score: 0
Accepted
time: 208ms
memory: 130960kb

input:

68777
224188 341389 951594398384
164769 448767 938384356181
143619 459268 208106564854
333627 436038 41801680018
34931 492990 399083027411
118353 444579 650503885091
217966 360265 366350177778
204955 337934 997053362793
383606 447984 615648721877
36796 303195 150165994357
287581 408047 974379752794
...

output:

296419906216663

result:

ok single line: '296419906216663'

Test #151:

score: 0
Accepted
time: 454ms
memory: 154720kb

input:

250000
249663 344086 769057368289
284632 331196 167315975694
283443 296102 954745059610
280637 333437 352584789976
25058 97432 271966410870
392662 488175 543276295838
95502 326421 287182475961
175361 434834 569490017032
86217 242804 365634138976
455670 493433 609180083187
17550 148068 432317663870
1...

output:

583396405645525

result:

ok single line: '583396405645525'

Test #152:

score: 0
Accepted
time: 439ms
memory: 155292kb

input:

250000
172257 387647 879461411373
172891 186869 236833931468
27165 55875 594332173496
186969 271944 609058706707
84701 226521 168625508336
261312 291225 545809240311
164418 389317 595001035679
68259 276990 270545405597
439938 461908 381066420047
33998 124053 838957792879
355676 432606 936770628872
2...

output:

590440687760372

result:

ok single line: '590440687760372'

Test #153:

score: 0
Accepted
time: 437ms
memory: 155704kb

input:

250000
239690 368945 839548525453
200132 340532 206936641681
432980 480458 948283149067
271346 324026 458843349014
121394 280663 246957330061
22394 275298 746450859098
61142 310229 440411565313
3473 204390 362720902375
157419 414038 448419809413
202291 384372 177022025842
180980 444076 212202434298
...

output:

594001926050583

result:

ok single line: '594001926050583'

Test #154:

score: 0
Accepted
time: 444ms
memory: 153300kb

input:

250000
17301 339211 375682614553
168312 204108 374427125804
61826 469025 49154245361
178532 218935 647234836937
285188 285839 415078827545
203891 393412 129620649825
350814 369597 912695386149
307136 482310 230063860107
79739 168309 886869083150
66887 497200 839763934362
74105 209935 911550699726
19...

output:

576780763236558

result:

ok single line: '576780763236558'

Test #155:

score: 0
Accepted
time: 448ms
memory: 156072kb

input:

250000
27588 388491 946621887850
120653 370073 40149666699
50249 183885 395177417382
28559 44468 724107503719
373469 496384 110286166327
322811 458760 292093072022
276364 298034 558598515812
10553 214543 7823860225
39381 467400 875393161548
123937 246975 367058733136
380449 444022 133018805556
10635...

output:

587882231836588

result:

ok single line: '587882231836588'

Test #156:

score: 0
Accepted
time: 458ms
memory: 154472kb

input:

250000
191581 312381 690764828479
160644 254950 181983487551
207411 304462 272360020007
186020 241046 308833088932
213386 358024 159646011501
224971 363410 306973676656
7792 280989 405190173107
250763 333523 27439063666
132850 372387 592634029742
295787 306577 732138652284
336949 452178 423286059086...

output:

592304021128923

result:

ok single line: '592304021128923'

Test #157:

score: 0
Accepted
time: 466ms
memory: 153860kb

input:

250000
415625 477598 915190586031
82751 300460 590969270688
110853 418219 128921518505
174512 381052 172418707188
190408 430188 829571908456
187068 454503 716032732992
281491 303187 340270512087
11727 223874 931159436735
47553 360951 251163859399
191627 286715 881210128425
70361 447439 67876276771
4...

output:

592571976161562

result:

ok single line: '592571976161562'

Test #158:

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

input:

250000
158398 273695 421893100017
358232 359895 505480672156
83442 152871 36482365023
202385 223765 740217437954
144561 199978 247571932578
193212 418788 521327427981
217577 437924 936434611235
356050 482808 695698335276
258802 412748 316205814429
275668 480315 360830952239
25475 328305 248430384623...

output:

568647645764461

result:

ok single line: '568647645764461'

Test #159:

score: 0
Accepted
time: 432ms
memory: 151704kb

input:

250000
135912 464465 574631546059
246333 489859 429799736871
22981 185530 376614279524
148801 289770 752662815256
61175 128587 546673513915
80723 84010 660878428821
86823 381223 239000040190
224395 348465 540748722715
84221 470723 721328002118
4386 24972 494141652712
177545 324011 426766787272
27523...

output:

574506440611829

result:

ok single line: '574506440611829'

Test #160:

score: 0
Accepted
time: 450ms
memory: 154060kb

input:

250000
33251 182533 956989097677
207091 231180 143002261189
149494 376179 995399352817
104221 331087 101307961300
332486 472549 985836076333
196120 306860 295190035259
263241 466449 416505587921
254270 326018 44758788471
26671 133711 940399413155
280446 457357 897157139538
4943 89889 246702622595
28...

output:

607345371296375

result:

ok single line: '607345371296375'