QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#272318#66. Two DishesDaiRuiChen007100 ✓1466ms183100kbC++141.0kb2023-12-02 16:52:552023-12-02 16:53:22

Judging History

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

  • [2023-12-02 16:53:22]
  • 评测
  • 测评结果:100
  • 用时:1466ms
  • 内存:183100kb
  • [2023-12-02 16:52:55]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5;
const ll inf=1e18;
ll a[MAXN],s[MAXN],p[MAXN],b[MAXN],t[MAXN],q[MAXN],ans=0;
vector <array<ll,2>> f[MAXN];
map <int,ll> dp;
inline void add(int id,ll val) {
	for(auto it=dp.lower_bound(id);val<0;it=dp.erase(it)) id=it->first,val+=it->second;
	dp[id]+=val;
}
signed main() {
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>a[i]>>s[i]>>p[i],a[i]+=a[i-1];
	for(int i=1;i<=m;++i) cin>>b[i]>>t[i]>>q[i],b[i]+=b[i-1];
	for(int i=1;i<=n;++i) if(s[i]>=a[i]) {
		int j=upper_bound(b+1,b+m+1,s[i]-a[i])-b;
		ans+=p[i];
		if(j<=m) f[i].push_back({j,-p[i]});
	}
	for(int j=1;j<=m;++j) if(t[j]>=b[j]) {
		int i=upper_bound(a+1,a+n+1,t[j]-b[j])-a;
		if(i<=n) f[i].push_back({j,q[j]});
		else ans+=q[j];
	}
	dp[m+1]=inf;
	for(int i=1;i<=n;++i) {
		sort(f[i].begin(),f[i].end(),[&](auto x,auto y){ return x[1]>y[1]; });
		for(auto k:f[i]) add(k[0],k[1]);
	}
	for(auto x:dp) if(x.first<=m) ans+=x.second;
	cout<<ans<<"\n";
	return 0;
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 155ms
memory: 68748kb

input:

200000 200000
278709225 90000000000000 119140441
16903947 90000000000000 50995483
544180428 90000000000000 38297640
196030639 90000000000000 34905015
488761573 90000000000000 161103211
679613271 90000000000000 17751356
966475096 90000000000000 46222110
551036816 90000000000000 155177091
587245324 90...

output:

107963696072360

result:

ok single line: '107963696072360'

Test #2:

score: 0
Accepted
time: 109ms
memory: 57644kb

input:

193493 200000
925058333 110000000000000 902655295
969346274 110000000000000 897063383
274276678 110000000000000 998492209
155091206 110000000000000 952470530
427199270 110000000000000 896313513
639254566 110000000000000 996267081
167829821 110000000000000 801226486
914764704 110000000000000 96254537...

output:

184676136004816

result:

ok single line: '184676136004816'

Test #3:

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

input:

200000 200000
78709225 90000000000000 119140441
16903947 90000000000000 50995483
144180428 90000000000000 38297640
196030639 90000000000000 34905015
88761573 90000000000000 161103211
79613271 90000000000000 17751356
166475096 90000000000000 46222110
151036816 90000000000000 155177091
187245324 90000...

output:

140049205271847

result:

ok single line: '140049205271847'

Test #4:

score: 0
Accepted
time: 157ms
memory: 61908kb

input:

193493 200000
982738968 110000000000000 102655295
803748915 110000000000000 97063383
901631098 110000000000000 198492209
970118580 110000000000000 152470530
873571720 110000000000000 96313513
957118364 110000000000000 196267081
992666794 110000000000000 1226486
857385432 110000000000000 162545375
95...

output:

73306782762089

result:

ok single line: '73306782762089'

Test #5:

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

input:

1 1
501529716 500000000 662608471
412844516 500000000 397784761

output:

397784761

result:

ok single line: '397784761'

Test #6:

score: 0
Accepted
time: 111ms
memory: 54444kb

input:

193648 189234
409900959 120000000000000 152145896
761018965 120000000000000 785003327
61396280 120000000000000 238026895
989062668 120000000000000 524504013
855153803 120000000000000 315249534
872338642 120000000000000 358968223
409250223 120000000000000 871827818
321869121 120000000000000 719848927...

output:

120307438151821

result:

ok single line: '120307438151821'

Test #7:

score: 0
Accepted
time: 44ms
memory: 43168kb

input:

1 200000
642993987 90000000000000 46073412
302380913 90000000000000 344682541
939348219 90000000000000 137977286
948161029 90000000000000 72596149
246590337 90000000000000 344586083
113422629 90000000000000 814150276
648901813 90000000000000 921420921
898034405 90000000000000 148425791
535266847 900...

output:

89969298579857

result:

ok single line: '89969298579857'

Test #8:

score: 0
Accepted
time: 36ms
memory: 41740kb

input:

200000 1
321566392 110000000000000 863747384
596772228 110000000000000 296502218
325454648 110000000000000 70164619
275895183 110000000000000 187787467
377086551 110000000000000 217279488
865517362 110000000000000 47298654
840579552 110000000000000 468914321
854986985 110000000000000 431496950
91797...

output:

99908911815069

result:

ok single line: '99908911815069'

Test #9:

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

input:

200000 200000
345286913 2000000000000000 376318746
219589528 2000000000000000 263352205
791814494 2000000000000000 77274228
580955195 2000000000000000 782313709
645431758 2000000000000000 781742022
20206380 2000000000000000 387136126
510328362 2000000000000000 953287814
819498100 2000000000000000 29...

output:

200001406161703

result:

ok single line: '200001406161703'

Test #10:

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

input:

200000 200000
1 200000 853767530
1 200000 755242887
1 200000 215803462
1 200000 101732824
1 200000 376828586
1 200000 690016218
1 200000 534818238
1 200000 648068478
1 200000 903957311
1 200000 809197499
1 200000 650941838
1 200000 867329819
1 200000 433581785
1 200000 586449792
1 200000 824550754
1...

output:

100000287734558

result:

ok single line: '100000287734558'

Test #11:

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

input:

200000 200000
3 6000000 928325552
1 6000000 743507163
5 6000000 106567808
5 6000000 494151314
4 6000000 291532803
2 6000000 163124810
3 6000000 760825535
4 6000000 272587154
4 6000000 352420321
4 6000000 905539622
5 6000000 620823619
4 6000000 604273601
1 6000000 770891408
5 6000000 999883946
4 6000...

output:

200153672337270

result:

ok single line: '200153672337270'

Subtask #2:

score: 3
Accepted

Test #12:

score: 3
Accepted
time: 3ms
memory: 39100kb

input:

12 12
884953730 1099691010 1
4015595 1477095709 1
726912949 2466785273 1
519508315 3990478241 1
708508942 5296800362 1
12364496 5320678730 1
286349693 6142173547 1
699837926 7037986902 1
934065390 8380990679 1
697606387 9347495140 1
875580140 10957110966 1
68179052 11776535162 1
344720591 838815847 ...

output:

12

result:

ok single line: '12'

Test #13:

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

input:

12 12
551691302 324632420 1
800582045 1348372403 1
14063803 14733602 1
52897269 256428825 1
153641504 1321745671 1
567834643 1337247037 1
453508034 1270193155 1
853479486 1945292068 1
949940012 170066870 1
931639209 404493902 1
527379143 3215826828 1
577323364 5341297473 1
454806733 35892194 1
54812...

output:

0

result:

ok single line: '0'

Test #14:

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

input:

12 12
286992568 900884294230763 1
522764708 179131135421401 1
858066681 221639310388039 1
411939222 616689146281519 1
278314510 411477603071162 1
736125071 481740908324652 1
314440633 586310260559054 1
992793856 538907614540791 1
734353326 623035949795417 1
240422976 537878602920600 1
225920052 3662...

output:

24

result:

ok single line: '24'

Test #15:

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

input:

12 12
560229147 876116411 1
762334640 1757956471 1
867292782 2271331496 1
513185346 2927972170 1
675220997 3573453786 1
452421504 4067817691 1
886937109 4734080537 1
711237939 5762262791 1
896169516 6500399725 1
182782794 6807543233 1
835794911 7462054577 1
100130164 7844981638 1
449688435 589791881...

output:

14

result:

ok single line: '14'

Test #16:

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

input:

12 12
958635898 253267141 1
157893686 685493591728951 1
976682032 720188590843821 1
790021767 2653778664 1
534783017 484912905 1
706987897 308457305655477 1
510148270 795920657967813 1
216566011 4754666709 1
288661613 728628635771894 1
856715472 883841683245416 1
81126924 4203988529 1
420966670 4746...

output:

19

result:

ok single line: '19'

Test #17:

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

input:

1 1
746491541 766814901 1
626145740 1256744672 1

output:

1

result:

ok single line: '1'

Test #18:

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

input:

12 12
450674304 2759730567 1
915813217 5865385994 1
429462295 1868112012 1
552626810 6878616256 1
521822262 2545854184 1
647591556 8576857974 1
530796658 132975736 1
97727387 8812772481 1
676240804 9699971390 1
193591298 6171207510 1
672069644 11153585817 1
218579173 6952631413 1
22151020 4121542856...

output:

14

result:

ok single line: '14'

Test #19:

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

input:

9 12
414814218 278771326 1
142790158 568604393 1
155567225 14012701 1
627555390 1224920860 1
677068511 5243031298 1
580933994 8598159379 1
819258172 1432469030 1
340548310 999347990 1
432162069 4373255579 1
99824657 11080715 1
756309567 9502204999 1
929699364 2343419815 1
376204577 6097684636 1
3995...

output:

6

result:

ok single line: '6'

Test #20:

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

input:

12 10
137685809 4249908213 1
888460570 6162167606 1
255401748 10310161799 1
574333708 5886505525 1
397332471 11008944494 1
68658609 10903747442 1
197555281 11638006542 1
944017921 12085863407 1
517938137 11772193793 1
775951900 14155878649 1
369629841 10039210915 1
856625908 11780413129 1
792090374 ...

output:

22

result:

ok single line: '22'

Test #21:

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

input:

12 12
1 10 1
1 1 1
1 13 1
1 7 1
1 11 1
1 7 1
1 18 1
1 17 1
1 21 1
1 19 1
1 18 1
1 18 1
1 1 1
1 13 1
1 6 1
1 8 1
1 15 1
1 3 1
1 14 1
1 16 1
1 15 1
1 10 1
1 21 1
1 15 1

output:

17

result:

ok single line: '17'

Test #22:

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

input:

12 12
1 16 1
2 28 1
2 14 1
3 25 1
3 39 1
2 14 1
3 21 1
1 32 1
1 43 1
1 23 1
3 24 1
3 30 1
2 37 1
2 9 1
3 29 1
2 35 1
1 16 1
2 2 1
2 31 1
1 22 1
2 35 1
1 20 1
3 21 1
1 38 1

output:

15

result:

ok single line: '15'

Test #23:

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

input:

12 12
89799642 49692259 1
229399564 811740996 1
135485930 841109682 1
431810470 9513334855 1
294721716 4487512793 1
324331816 5359589182 1
478365662 3315887541 1
47534872 4309614247 1
205679728 5535047461 1
791160453 1200926698 1
614191623 5057551186 1
764668366 10713756692 1
685693506 2750639180 1
...

output:

15

result:

ok single line: '15'

Test #24:

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

input:

5 12
776828142 1397545734 1
189506344 2160364868 1
58596121 5966553855 1
272883209 1139924761 1
45729954 5446434658 1
927047364 68907031 1
68493905 1982484482 1
512459772 1263184765 1
774136355 6191784333 1
396934216 5374853900 1
667853683 6656165826 1
580790148 8440557419 1
298336860 6088273637 1
7...

output:

10

result:

ok single line: '10'

Test #25:

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

input:

12 3
538372153 2607291479 1
17670010 360747035 1
715398730 881558330 1
212550828 3547752331 1
448734103 3475078328 1
243463405 4013385464 1
822213572 2805893143 1
109881706 6004746417 1
701427369 5274623662 1
125209451 5783604167 1
589280031 5401871987 1
351006393 5098345877 1
570369185 4699950172 1...

output:

10

result:

ok single line: '10'

Test #26:

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

input:

8 12
466421672 322419685 1
829839951 10803101238 1
43196804 2794274548 1
743316313 5015041198 1
798441550 6185579270 1
767420588 11240247616 1
39283192 5491197636 1
184273471 368244362 1
558308306 1222463139 1
893919920 1809209594 1
4053601 2761904900 1
813073191 5927619356 1
645542021 2085805592 1
...

output:

12

result:

ok single line: '12'

Test #27:

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

input:

12 4
979929308 3107436230 1
428664578 3323216326 1
914625879 2756659832 1
404226469 6714121618 1
581278541 6543352379 1
362841137 7530929877 1
32024229 4571060808 1
435623827 7843360378 1
920715456 7745344797 1
205825433 7953967897 1
455568658 8391536383 1
946687914 10252503424 1
993197404 974833302...

output:

14

result:

ok single line: '14'

Subtask #3:

score: 7
Accepted

Dependency #2:

100%
Accepted

Test #28:

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

input:

1999 2000
515391161 763795702 1
611274809 1261562553 1
241579177 1638313844 1
794330740 2675506869 1
10171859 2788754450 1
421070901 3085449583 1
191803444 3359041514 1
462515964 3413105535 1
942558211 4921260476 1
789307312 5230580771 1
749632607 6428848493 1
168283015 6307563953 1
741578406 725117...

output:

3006

result:

ok single line: '3006'

Test #29:

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

input:

2000 2000
977045956 471656263488432 1
164570698 544516146950584 1
184755663 49641816362108 1
365443392 950619563758866 1
688612912 611528357573017 1
603003602 167178849837844 1
845988325 45666940 1
69841518 389869119824197 1
124418966 599032577331771 1
495851703 1795343372 1
221534905 8803126 1
9258...

output:

3010

result:

ok single line: '3010'

Test #30:

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

input:

2000 2000
888945549 6597059176 1
428603708 95966025326 1
383232136 897851857457 1
695719431 574325043037 1
225206990 575657684068 1
308184262 923436400625 1
628525462 1132053696837 1
842180289 75628606376 1
95193624 84640375432 1
254757702 571142915018 1
542955837 119322101239 1
252366421 1158754289...

output:

2145

result:

ok single line: '2145'

Test #31:

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

input:

2000 1853
670674530 50926657892 1
495195316 419655531680 1
490372978 512122889 1
797821088 1385196699 1
23160229 328741921 1
70776335 1789689959 1
762368375 108629421906 1
698037053 943239738989 1
455709554 1931258015 1
47888549 508584001806 1
845792326 785954126530 1
820951574 2458901941 1
54455538...

output:

1088

result:

ok single line: '1088'

Test #32:

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

input:

1924 2000
756701266 894992938839 1
817177749 1855254325724 1
572689391 679942344598 1
99996538 585203661251 1
642038567 749454653215 1
617775243 730582259743 1
853124406 694062360970 1
399454416 514938074685 1
44070185 854472820813 1
210538665 941352354205 1
997350872 626596196929 1
988218611 550753...

output:

3218

result:

ok single line: '3218'

Test #33:

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

input:

2000 2000
1 442 1
1 505 1
1 1053 1
1 549 1
1 1300 1
1 631 1
1 1367 1
1 1400 1
1 936 1
1 941 1
1 1558 1
1 1126 1
1 1271 1
1 377 1
1 1316 1
1 1125 1
1 1028 1
1 1042 1
1 644 1
1 892 1
1 1762 1
1 1650 1
1 878 1
1 337 1
1 2021 1
1 149 1
1 167 1
1 607 1
1 325 1
1 805 1
1 433 1
1 339 1
1 1342 1
1 271 1
1 1...

output:

2090

result:

ok single line: '2090'

Test #34:

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

input:

2000 2000
1 4860 1
4 6954 1
2 3697 1
3 2870 1
1 4275 1
3 351 1
1 3694 1
3 220 1
1 3285 1
4 356 1
2 7431 1
3 341 1
3 1502 1
2 4086 1
3 1644 1
1 3112 1
5 2329 1
4 2312 1
4 1914 1
3 5974 1
1 485 1
4 1502 1
3 3334 1
3 5229 1
3 4352 1
1 4328 1
5 2116 1
4 1841 1
1 4584 1
1 3830 1
1 439 1
1 3602 1
2 2542 1...

output:

2113

result:

ok single line: '2113'

Subtask #4:

score: 39
Accepted

Dependency #3:

100%
Accepted

Test #35:

score: 39
Accepted
time: 87ms
memory: 54004kb

input:

200000 200000
997698065 1023821866 1
269692358 1389349329 1
607170799 1944366847 1
516351186 2485184379 1
935984256 3362372522 1
899165316 4310826413 1
231654824 4495598131 1
951113023 5443901040 1
844276634 6326886390 1
397634275 6655091165 1
272944023 7018964189 1
356674362 7343600279 1
331036300 ...

output:

300187

result:

ok single line: '300187'

Test #36:

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

input:

200000 199999
864888449 321413767 1
473961621 170106790 1
190522959 951283046552705 1
820646665 186049068 1
22301217 650696254682916 1
9492513 491822481857728 1
860062372 275051916431383 1
37064228 376546475720216 1
902791815 498850717553358 1
391795076 219084122442958 1
731578247 5280185010 1
19718...

output:

300064

result:

ok single line: '300064'

Test #37:

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

input:

199999 199999
458162947 611595642 1
175643977 1338679925 1
727270078 2680353136 1
122110004 3545231242 1
24786112 3686263336 1
260954842 4113010463 1
378646915 4703058111 1
422692851 5845217248 1
377845733 6346336935 1
473430752 6963508264 1
468331006 7771729732 1
663764144 8849508308 1
327593225 95...

output:

299919

result:

ok single line: '299919'

Test #38:

score: 0
Accepted
time: 140ms
memory: 64496kb

input:

200000 200000
579688376 382937363 1
471315639 899565849 1
73440809 555439640 1
909550586 113290738631549 1
860952046 358362661 1
759672613 375691126576003 1
718627966 1892055940 1
499195004 112270615930314 1
770008372 1388465102 1
236201261 1682259346 1
100210626 4041567770 1
445253931 1320635327 1
...

output:

300136

result:

ok single line: '300136'

Test #39:

score: 0
Accepted
time: 100ms
memory: 51268kb

input:

200000 200000
438384814 46599373446280 1
242632531 277458945797670 1
11446033 330799469008789 1
709180318 83267994913452 1
31970981 276704195932692 1
447769525 94582759778718 1
72132404 290312525868845 1
99284585 81622772318080 1
628120785 297071546680934 1
93794542 295899099544911 1
611381209 87429...

output:

300588

result:

ok single line: '300588'

Test #40:

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

input:

200000 200000
587199200 2000000000000000 1
532201403 2000000000000000 1
8872164 2000000000000000 1
443390545 2000000000000000 1
467817920 2000000000000000 1
174720507 2000000000000000 1
54297826 2000000000000000 1
425639335 2000000000000000 1
465114681 2000000000000000 1
95069547 2000000000000000 1
...

output:

400000

result:

ok single line: '400000'

Test #41:

score: 0
Accepted
time: 216ms
memory: 59072kb

input:

200000 200000
334632844 16274135177545 1
386622774 50825326034155 1
528258658 99522299039877 1
766408591 61303770451401 1
570739595 171555294489520 1
667500508 93249094472292 1
179586402 30463513919334 1
281562532 16296376914732 1
567999721 29972540915638 1
546396559 85129477176116 1
180410887 27877...

output:

201428

result:

ok single line: '201428'

Test #42:

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

input:

1 200000
30737772 16040363054787 1
494146605 507694953 1
163611368 1407558367 1
683331429 2007373418 1
340542838 1703085043 1
334270729 2036082570 1
991956413 3036656159 1
2310435 3458899995 1
580894798 3744096166 1
741415473 4334119063 1
619691605 4953269049 1
696651907 6642477271 1
322946088 65783...

output:

200000

result:

ok single line: '200000'

Test #43:

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

input:

200000 1
799822153 964760988 1
782914217 2578125684 1
55647649 2592763578 1
15876266 2021821485 1
162716476 2785976431 1
494720504 3065835685 1
510051845 3018669633 1
296011315 4078601297 1
376532888 4472065797 1
168832432 4615664799 1
348315196 4966906111 1
305981374 4333429946 1
382367095 56138158...

output:

200000

result:

ok single line: '200000'

Test #44:

score: 0
Accepted
time: 143ms
memory: 54456kb

input:

195334 200000
843788521 654129118 1
960847714 1587160327 1
9430464 6523301011940 1
258842065 44989057948944 1
2226930 27275934362292 1
589574674 84670108883770 1
125533909 29562223400269 1
520539817 17803049549481 1
417673920 81802292249664 1
792900148 1618317625 1
297414109 48789244501832 1
1152717...

output:

102490

result:

ok single line: '102490'

Test #45:

score: 0
Accepted
time: 179ms
memory: 62904kb

input:

200000 191356
925336928 87880463370406 1
923267791 83412632831090 1
129505888 62799307192343 1
930021102 73763309250581 1
146259111 56173403220375 1
785710560 50788653176448 1
887208389 82022243196678 1
864696811 56257468610049 1
257475306 73060572624940 1
914162993 54994621169238 1
620473425 614869...

output:

316088

result:

ok single line: '316088'

Test #46:

score: 0
Accepted
time: 211ms
memory: 60372kb

input:

200000 200000
1 110406 1
1 59975 1
1 10273 1
1 112698 1
1 3692 1
1 101653 1
1 188043 1
1 112899 1
1 91299 1
1 172752 1
1 73143 1
1 27778 1
1 143816 1
1 156891 1
1 175497 1
1 122312 1
1 70482 1
1 35635 1
1 123323 1
1 48765 1
1 130348 1
1 193361 1
1 24581 1
1 9 1
1 150953 1
1 186357 1
1 171174 1
1 997...

output:

201561

result:

ok single line: '201561'

Test #47:

score: 0
Accepted
time: 214ms
memory: 59868kb

input:

200000 200000
1 505013 1
2 498364 1
4 339881 1
2 121130 1
2 467399 1
1 487606 1
4 596447 1
4 364921 1
3 550540 1
4 299871 1
4 403863 1
4 919469 1
3 534862 1
5 385306 1
1 448036 1
4 10887 1
1 30645 1
3 453776 1
1 411223 1
2 145918 1
4 367602 1
3 266556 1
2 468652 1
2 231923 1
1 445193 1
4 354546 1
3 ...

output:

201501

result:

ok single line: '201501'

Subtask #5:

score: 11
Accepted

Dependency #4:

100%
Accepted

Test #48:

score: 11
Accepted
time: 100ms
memory: 52392kb

input:

200000 200000
298961082 99761086323151 129806250
363519903 99760889469672 313979789
990863132 99761447918630 902271296
391598048 99761319415609 152470327
540262746 99761610624631 651450226
666620136 99761373781623 353383972
712170125 99761468231150 467094922
406883722 99761198254106 783474893
697848...

output:

149953856090579

result:

ok single line: '149953856090579'

Test #49:

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

input:

200000 200000
944874833 946150044455271 727294723
417567478 748491508 459351221
336356835 828571586103954 458589605
833384570 1619001793 697090447
765243167 3106816218 66633140
238656010 707018528641705 950403061
423619866 1278554966 323231564
1760010 3738784657 211694719
526864286 841679911993449 3...

output:

149597616748329

result:

ok single line: '149597616748329'

Test #50:

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

input:

200000 200000
79122220 99746040374574 1
850909973 99746584099672 1
498975192 99746782287572 1
87960186 99746559294326 1
845841575 99746747474090 1
196688005 99746458511062 1
967089520 99747262416653 1
86349390 99747209213280 1
443735765 99747229126416 1
904722601 99747861885713 1
307740570 997476925...

output:

1000199999

result:

ok single line: '1000199999'

Test #51:

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

input:

200000 200000
214756303 99853927379101 1367
32288894 99853183214635 2482
525933331 99853536099138 1360
951805423 99854405206763 721
832749071 99854628701592 2497
802453831 99855247631989 2353
157869747 99854969067715 2435
599001295 99855114647840 1271
736231122 99855475770989 683
486925107 998555188...

output:

1000199999

result:

ok single line: '1000199999'

Test #52:

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

input:

1 1
972394581 1246249626 784434497
959741939 1942914328 731917398

output:

1516351895

result:

ok single line: '1516351895'

Test #53:

score: 0
Accepted
time: 239ms
memory: 60048kb

input:

200000 200000
717365271 29925592708320 308562580
630039019 529794789 625894349
418530142 60648991876010 411808089
656902465 66605091046374 489609961
110861088 2929935147601 833887701
646662239 62356552846442 645773506
118179280 19712043567294 902204536
853883235 76973979740553 579052677
334093544 70...

output:

100893398485842

result:

ok single line: '100893398485842'

Test #54:

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

input:

193628 200000
927534154 77454246516931 302894118
486905813 562354234 964686424
301650160 38336964063397 927092701
811250388 86749766892777 56981404
192051373 23228327574473 253514699
517856587 92758394725578 988501656
67952327 56930215241463 14300877
539441344 1407516441 719572225
151306106 10206491...

output:

51288994128593

result:

ok single line: '51288994128593'

Test #55:

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

input:

200000 189534
750514588 134734557272549 211180370
877350718 72776912291896 259060775
127971537 93324271792485 621204726
229471367 62824197480932 323051827
87827098 140669726952077 957855133
157568818 63621149862636 35432817
733509562 154756366309607 674953835
101495140 59560197369762 32585598
738379...

output:

158056872743750

result:

ok single line: '158056872743750'

Test #56:

score: 0
Accepted
time: 223ms
memory: 58528kb

input:

200000 200000
1 132162 114080239
1 156879 525699517
1 75714 685935769
1 199770 85640256
1 91927 683084722
1 10385 295290959
1 68715 257667384
1 61359 263520230
1 48377 760825038
1 109070 746783604
1 89594 82670283
1 184278 375645260
1 169160 566085489
1 142849 806111546
1 200015 30564949
1 14067 369...

output:

100949563486806

result:

ok single line: '100949563486806'

Subtask #6:

score: 9
Accepted

Dependency #5:

100%
Accepted

Test #57:

score: 9
Accepted
time: 465ms
memory: 104924kb

input:

1000000 1000000
245790387 499397236501752 783985746
296284224 499397297805808 886109037
368089759 499397406786446 87383438
81723212 499397101634699 150908236
527628951 499396983654314 665942850
931868062 499397289563114 323373722
64671922 499396967304215 697407570
984788017 499396931371976 934282385...

output:

750178018675788

result:

ok single line: '750178018675788'

Test #58:

score: 0
Accepted
time: 794ms
memory: 167476kb

input:

1000000 1000000
993024457 831817339 246075049
108477765 821393486525128 795361323
465911276 949557144184681 191106236
69953800 932950073319595 262330738
723189403 611874141920373 665353071
659071024 667076690 90226002
668896933 649269788220681 773344095
831403976 699473596306998 770391908
271630523 ...

output:

749540199817851

result:

ok single line: '749540199817851'

Test #59:

score: 0
Accepted
time: 1082ms
memory: 183100kb

input:

1000000 1000000
719037809 500708402042158 1
66683481 500707726230726 1
204972353 500707691288967 1
310481632 500707417732187 1
395476241 500707640735207 1
72478712 500707462227929 1
563807173 500707575893194 1
653976464 500707985488501 1
625565205 500707868010573 1
112954134 500706943316541 1
388240...

output:

1000999999

result:

ok single line: '1000999999'

Test #60:

score: 0
Accepted
time: 522ms
memory: 120656kb

input:

1000000 1000000
688875491 499960328350507 382
932433934 499961092415658 429
833003565 499961884681851 104
55719061 499961021546288 336
646386122 499961611783706 424
280728089 499961350169068 477
341324166 499961037702454 155
431106913 499961196889471 115
264299866 499960685536187 297
620511003 49996...

output:

1000999999

result:

ok single line: '1000999999'

Test #61:

score: 0
Accepted
time: 1415ms
memory: 131648kb

input:

1000000 1000000
30768332 197575477068518 277598106
516710967 545587678896187 600106326
215083384 140048927814854 943607196
882229596 100833873459543 218010258
608157547 194472567386407 41056675
551405396 95645664763564 193062599
574244455 35824950674560 20930826
93507086 464061304589142 342953217
38...

output:

501791904267381

result:

ok single line: '501791904267381'

Test #62:

score: 0
Accepted
time: 843ms
memory: 100072kb

input:

934518 1000000
996565221 398131428678052 839860855
142111968 136016286495538 26110182
655529905 180045703043073 614142096
280000160 446164518633608 913682106
268931158 157465433380039 806742704
263906758 2340955438 974911771
949833096 23816203464985 80679994
286014515 184410360964700 217657122
37592...

output:

254376259023502

result:

ok single line: '254376259023502'

Test #63:

score: 0
Accepted
time: 1277ms
memory: 138264kb

input:

1000000 883248
883146129 449094758199823 698545970
91173925 361705745940050 91874133
129603845 838712483877822 406916135
640209620 846744904901006 419363195
455685184 292410892343279 476596229
656372704 427100526315466 3692065
687918730 389640954837743 803434479
978686873 780546058598738 120620287
2...

output:

782964237020590

result:

ok single line: '782964237020590'

Test #64:

score: 0
Accepted
time: 1312ms
memory: 129572kb

input:

1000000 1000000
3 1272690 590684434
4 503612 424507278
5 441340 294340782
5 1547172 499551424
4 1023720 797189962
5 3918494 121378046
2 774495 559332189
2 1196508 223151041
5 1379407 447892996
3 2514854 748950734
1 1919280 575741865
1 3395 848465921
2 1803987 414033904
4 1946403 967342620
4 2781741 ...

output:

502373630539657

result:

ok single line: '502373630539657'

Subtask #7:

score: 17
Accepted

Dependency #1:

100%
Accepted

Dependency #5:

100%
Accepted

Test #65:

score: 17
Accepted
time: 157ms
memory: 64176kb

input:

200000 200000
580334908 807216617 -444115777
632498256 1562870708 -403317872
820316400 3319637010 -706885497
821259216 4225595444 -590247019
853162668 5329885238 -519687773
7380790 5810916565 -449649957
926652658 7252255001 -696197765
392575810 7810762663 -28955078
968347369 9471731839 -209377056
62...

output:

-50120573402371

result:

ok single line: '-50120573402371'

Test #66:

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

input:

200000 200000
257497130 26049067 -467812377
405835060 400501780390623 -3353773
561469001 528255018350824 -255631407
278268250 226311293309100 -119132567
567410269 143063310136366 -127456196
424061057 1216664493 -520081162
37399348 970021648130172 -308622651
4203360 427861483825456 -603215684
3712245...

output:

-49939200178148

result:

ok single line: '-49939200178148'

Test #67:

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

input:

200000 200000
855641178 100096279421823 -1000000000
372252229 100095978888452 680
285187830 100095421572212 269
216593951 100095433305475 187
346667678 100095171158667 470
164647511 100095323540599 931
933541613 100095856483129 761
247317341 100095241900617 643
216116602 100095274815762 165
18329419...

output:

-166897385

result:

ok single line: '-166897385'

Test #68:

score: 0
Accepted
time: 191ms
memory: 69784kb

input:

200000 200000
930523876 100220583494363 -927
863722482 100221149336653 -397
847389572 100221549896885 -537
786672166 100221558808814 -860
435867293 100221926285150 -168
874014006 100222514467296 -406
537380763 100222688989848 -91
639126688 100222921858949 -928
935142940 100222836679477 -1352
4966014...

output:

-166672857

result:

ok single line: '-166672857'

Test #69:

score: 0
Accepted
time: 326ms
memory: 71504kb

input:

200000 200000
138591463 15703457487028 0
373586645 77531518093699 0
424398499 38136893217585 0
236902938 8885235852568 0
637798275 55292643066162 0
189810397 16195073815285 0
648982932 46262310416719 0
729656372 55572504861651 0
760735729 60012822128998 0
761442076 6785063209842 0
115215630 92987899...

output:

0

result:

ok single line: '0'

Test #70:

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

input:

1 1
468512468 748325173 705717094
459901058 830104491 -971967427

output:

705717094

result:

ok single line: '705717094'

Test #71:

score: 0
Accepted
time: 246ms
memory: 58484kb

input:

200000 200000
845376622 30828959862729 393370561
726124048 64829216214148 492723478
180555445 82608613197623 35029901
279045873 78296473066390 581033093
173634675 89178652396744 736910856
938368695 8915848929000 -239389872
259133077 26031824389483 759921145
34550648 92490028510696 418671419
98207279...

output:

40861684665895

result:

ok single line: '40861684665895'

Test #72:

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

input:

200000 192359
378414660 248996381 953702940
575107438 77482520600928 923587576
382419234 163850265002289 740741240
215628283 612847335 -716035814
274195100 85104842986326 -311366615
284775847 13297291647292 219169339
976091849 4893788 535302148
993263890 95976595789771 3948201
378223821 808217564199...

output:

31326658788976

result:

ok single line: '31326658788976'

Test #73:

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

input:

189354 200000
391735487 71873187481502 891092135
927649723 54172840029209 -90856479
653136155 83496076610803 489099759
364697492 82154832542014 -949875354
158616831 51048991661800 284569845
162945090 60967759780538 805526534
41572239 92317119301529 -307162093
915368399 111041273115626 -794806120
443...

output:

31919935866825

result:

ok single line: '31919935866825'

Test #74:

score: 0
Accepted
time: 220ms
memory: 57864kb

input:

200000 200000
3 144743 352871734
5 413265 -276869323
5 290482 -131298509
4 494650 -506969942
5 567208 287206022
5 5 399144334
1 362175 881619360
3 23912 724506439
5 570501 583130846
1 257386 -412498208
3 355302 228829348
2 572167 158906339
5 509728 -68005943
2 197839 774596778
4 286921 882307893
2 5...

output:

31231422581637

result:

ok single line: '31231422581637'

Subtask #8:

score: 9
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Dependency #7:

100%
Accepted

Test #75:

score: 9
Accepted
time: 851ms
memory: 167420kb

input:

1000000 1000000
126117083 488653800 -273869083
718209624 1497997444 -701209902
720605250 3044388034 -458745698
503507132 3928522989 -752337541
620116463 5243647752 -8066002
38631680 5525563658 -38238256
369456806 6181139840 -890483709
83051387 6479680762 -449872107
575805389 7761164090 -851209587
16...

output:

-249959330604131

result:

ok single line: '-249959330604131'

Test #76:

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

input:

1000000 1000000
47015483 956229305267217 -318352900
968545972 475621877 -838145315
912734744 1189126520 -802138552
462897372 1306928034 -690768481
920071607 725633315258449 -160413358
987486935 183743617 -944669900
486570279 793882777165464 -900188588
828518021 3546953620 -709373896
582676757 681621...

output:

-249637774723945

result:

ok single line: '-249637774723945'

Test #77:

score: 0
Accepted
time: 560ms
memory: 120696kb

input:

1000000 1000000
995396130 499666537652332 -1000000000
539384716 499666815480543 272
797054422 499667288560907 28
171809683 499666981953443 97
956735987 499667778398821 192
716100335 499668354924069 269
499070800 499668648546738 241
336858784 499668727715995 280
729582693 499669197559733 211
46943810...

output:

-167150129

result:

ok single line: '-167150129'

Test #78:

score: 0
Accepted
time: 1111ms
memory: 183048kb

input:

1000000 1000000
659055121 500021010425923 -289
295863189 500020681315696 -330
770965996 500021225186941 -319
173412763 500020911671750 -133
703368303 500020669586179 -268
761533950 500020673703265 -58
717600643 500020861835133 -108
904137324 500021518890244 -41
478820932 500021383562000 -56
83221529...

output:

-167015284

result:

ok single line: '-167015284'

Test #79:

score: 0
Accepted
time: 1466ms
memory: 131676kb

input:

1000000 1000000
908216743 202504871211765 815074999
558872235 406092775811330 488631364
413168085 131974698442193 955664469
967529927 499903590624517 521402379
452809628 465157718735705 688006065
821057591 432971418474925 152081890
898885998 290640922252444 441691511
802092172 495897779895573 875328...

output:

202063463357305

result:

ok single line: '202063463357305'

Test #80:

score: 0
Accepted
time: 793ms
memory: 100056kb

input:

1000000 934589
375430966 36823924 387997587
645867099 927229516 976866474
395607968 120490442520917 985362889
453979815 872613599 67499923
7774226 1051268307 439785823
165946017 122483597989393 368531834
160984227 278999555306379 963544682
319987971 354128029335973 147913869
76731574 347325541103656...

output:

127756295303467

result:

ok single line: '127756295303467'

Test #81:

score: 0
Accepted
time: 1093ms
memory: 118948kb

input:

892324 1000000
728344879 289072837203634 -107407387
363140912 469244215215798 137939188
145955904 436457316888782 -892099139
851893672 970279862282859 806777481
580170653 299922997002645 149380100
404196747 679357818211644 900708476
101651083 385401666037553 718649693
379159903 980062247066922 31280...

output:

236006357456318

result:

ok single line: '236006357456318'

Test #82:

score: 0
Accepted
time: 1388ms
memory: 130980kb

input:

1000000 1000000
1 735973 738092933
1 416560 101377061
1 263017 -658303804
1 784339 651770275
1 566532 437105081
1 515190 150336378
1 728513 596793704
1 479088 701500523
1 702471 705532766
1 961133 -865343418
1 794421 423833492
1 274352 514468862
1 62649 953661997
1 320479 -34079397
1 57966 364989651...

output:

252112613912371

result:

ok single line: '252112613912371'

Test #83:

score: 0
Accepted
time: 1373ms
memory: 127464kb

input:

1000000 1000000
652885 144453059524 -130816762
510455 378831316412 915577449
873513 27332886221 109736103
666030 295407070195 298210161
535093 497002911455 315971380
681335 484598868632 614408936
668646 321852048251 59900844
201605 693702856350 -788049486
848828 716913642470 176898611
571070 3485688...

output:

201708839726646

result:

ok single line: '201708839726646'

Extra Test:

score: 0
Extra Test Passed