QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133514#4933. Cul-De-Sac ParadesDelay_for_five_minutes#AC ✓41ms15896kbC++141.1kb2023-08-02 10:29:172023-08-02 10:29:20

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 10:29:20]
  • Judged
  • Verdict: AC
  • Time: 41ms
  • Memory: 15896kb
  • [2023-08-02 10:29:17]
  • Submitted

answer

#include<bits/stdc++.h>
#define maxn 100005
long long dp[maxn][2];
std::vector< std::pair<int,int> > G[maxn];
int root;
void dfs(int u,int fa) {
    dp[u][0] = 0;
    dp[u][1] = -1e18;
    if (G[u].size() == 1) {
        dp[u][1] = 0;
    }
    for(auto i:G[u]) if (i.first != fa) {
        int v = i.first, w = i.second;
        dfs(v,u);
        long long t0,t1;
        t0 = std::max(dp[u][0] + dp[v][0], dp[u][1] + dp[v][1] + w);
        t1 = std::max(dp[u][0] + dp[v][1] + w, dp[u][1] + dp[v][0]);
        dp[u][0] = t0;
        dp[u][1] = t1;
    }
}
int main() {
    // freopen("in.txt","r",stdin);
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        G[x].push_back({y,w});
        G[y].push_back({x,w});
    }
    if (n==2) {
        printf("%d\n",G[1].begin() -> second);
        return 0;
    }
    for(int i=1;i<=n;i++) {
        if (G[i].size() > 1) {
            root = i;
            break;
        }
    }
    dfs(root,0);
    printf("%lld\n",dp[root][0]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

10
1 5 10
2 5 20
3 6 20
4 7 40
5 6 50
5 8 30
6 7 10
6 9 20
7 10 40

output:

210

result:

ok single line: '210'

Test #2:

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

input:

7
1 2 10
1 3 5
2 4 15
2 5 20
3 6 12
3 7 13

output:

60

result:

ok single line: '60'

Test #3:

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

input:

2
1 2 999999

output:

999999

result:

ok single line: '999999'

Test #4:

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

input:

99998
61574 86615 797406
60311 82587 178465
19859 34640 276785
72152 85828 522827
63954 75374 850271
34650 70761 614751
54383 62797 629594
53488 67239 635059
1068 90407 761165
45772 99711 631843
30223 31223 526803
47414 48701 449980
53513 72085 619930
25145 30368 639945
15607 56956 41970
70523 75794...

output:

50128350436

result:

ok single line: '50128350436'

Test #5:

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

input:

99991
44118 49593 16384
15356 67039 65536
24585 93536 8192
44789 61153 4096
52518 64816 4096
21074 67059 131072
45119 84954 2048
81532 87268 8
53156 57083 1024
2920 69488 16384
17414 85108 128
59363 68792 128
65869 81742 262144
4399 62293 8
75434 94336 512
59222 74011 1024
28904 44996 8192
22870 520...

output:

5180152568

result:

ok single line: '5180152568'

Test #6:

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

input:

99990
43373 94529 6765
43512 95580 3
9952 47373 144
2122 75544 610
65257 98541 1
83399 84892 46368
62899 80229 3
19423 67414 317811
1416 10614 75025
14092 75842 55
28940 70971 514229
61861 70122 196418
24460 77932 3
60271 83567 196418
25481 31043 3
59358 84305 2
79865 86381 75025
22049 62698 6765
11...

output:

7290528623

result:

ok single line: '7290528623'

Test #7:

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

input:

99993
473 75124 470182
31726 74809 273323
20021 31121 544979
17323 93058 765660
8957 39382 477026
32988 88211 906071
15148 96747 302098
16948 30008 288769
23301 90681 4538
9787 99475 990543
1436 15226 276169
3195 46005 414252
16045 18611 538955
39696 87655 349895
24049 97207 332354
39356 81930 19409...

output:

46386433947

result:

ok single line: '46386433947'

Test #8:

score: 0
Accepted
time: 32ms
memory: 12196kb

input:

99993
47089 63847 524288
67663 90637 128
47324 55902 2048
69072 83922 2048
4283 52508 256
10414 63302 2048
3697 21676 4096
37264 54660 524288
28030 80072 16
48406 69098 4
8844 88543 262144
54774 76617 1024
91060 99195 131072
64564 68401 4096
56146 73009 512
39039 42729 4
21192 79050 4
50550 61464 81...

output:

5169373629

result:

ok single line: '5169373629'

Test #9:

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

input:

99994
3948 52816 196418
26918 85773 377
46603 81349 10946
29449 68249 987
4878 53667 233
13882 62962 1597
54236 57928 21
5280 36451 55
1907 72566 46368
46711 81010 987
66485 99611 1
30645 75621 4181
24032 85789 13
7358 58633 4181
52883 74280 1
10117 95522 1
18601 23710 1597
20626 46068 832040
28326 ...

output:

7289064589

result:

ok single line: '7289064589'

Test #10:

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

input:

99995
41506 79577 29707
19393 30753 561756
50728 95616 749617
15344 92734 962144
33253 71769 105059
9205 64699 539904
45592 98060 459643
29375 31390 747664
69802 89614 819163
26477 27980 289981
17994 22352 179331
58879 60347 634314
24920 97435 283903
6256 14633 67878
35697 53026 87101
29665 65545 20...

output:

49926880417

result:

ok single line: '49926880417'

Test #11:

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

input:

99997
60580 70091 2048
44513 63334 4
20396 70465 128
38186 84662 65536
15045 21253 2048
442 86045 262144
8368 77814 131072
60156 71863 4
28933 35448 65536
21908 30027 32
27728 76318 16
78534 99286 16
51864 80169 128
25567 37981 1
21831 30117 4096
46688 47876 8
66145 95903 8192
63737 73076 1
12579 67...

output:

5244131327

result:

ok single line: '5244131327'

Test #12:

score: 0
Accepted
time: 35ms
memory: 12040kb

input:

100000
18221 57181 8
28466 76155 144
9858 70413 832040
65725 72484 21
47413 92084 610
57372 64004 610
30461 62988 377
23644 54197 55
5180 23450 610
40331 47253 75025
4964 17132 4181
39453 71021 28657
18867 90400 75025
71033 92492 75025
14423 90923 121393
76190 86008 6765
7950 94798 75025
17361 31202...

output:

7163888319

result:

ok single line: '7163888319'

Test #13:

score: 0
Accepted
time: 41ms
memory: 11596kb

input:

99995
71806 78902 147231
69729 81587 252334
34293 46522 543870
81082 88699 472219
52644 75043 306910
66236 79204 92214
7390 86599 464361
19693 73333 503163
40358 54646 502512
36281 96266 415986
74559 86084 943027
10184 50409 66691
27640 79167 161966
67724 95438 242270
40646 74399 966097
30578 40414 ...

output:

47915993752

result:

ok single line: '47915993752'

Test #14:

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

input:

6
1 2 50
2 3 99
2 4 50
3 5 50
3 6 50

output:

200

result:

ok single line: '200'

Test #15:

score: 0
Accepted
time: 41ms
memory: 11684kb

input:

99992
39187 45878 4
90492 97988 32768
45370 87412 16
44416 86313 1
21945 45260 32768
22065 77091 1
6644 8610 1024
8622 24321 65536
20340 32855 1
5647 98998 64
39304 87641 32768
27607 27912 65536
39392 63961 65536
65251 79799 8
28004 63936 524288
492 35013 131072
50382 54409 16384
17292 83975 16384
2...

output:

5255002924

result:

ok single line: '5255002924'

Test #16:

score: 0
Accepted
time: 31ms
memory: 11588kb

input:

99998
32130 71028 46368
53096 66254 1
64681 90243 4181
3340 46380 987
52914 69008 987
7435 26972 21
14114 33449 75025
35903 37565 8
8284 95718 55
43479 51910 13
47114 66674 196418
37061 38157 121393
1661 5073 2584
42860 83123 2
16124 16829 75025
35370 70126 610
61968 82491 233
46152 72383 1597
34829...

output:

7277463159

result:

ok single line: '7277463159'

Test #17:

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

input:

100000
22357 42312 308782
10106 18739 203814
89857 99840 552873
8253 51278 140666
31060 85397 825496
68234 88821 529473
23127 83717 126357
51278 69078 359176
10106 36510 698329
31060 53006 276422
50886 89857 649655
82952 95686 48967
14070 42366 113143
31060 62752 18324
65366 68234 546655
2934 97783 ...

output:

50089239408

result:

ok single line: '50089239408'

Test #18:

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

input:

100000
66893 75929 12321
76572 82268 772641
47681 76500 261121
11987 16486 483025
30840 44352 919681
42757 89957 190096
40507 64881 75625
1473 66893 580644
3812 14387 474721
76572 83254 4624
93459 97553 416025
55613 75312 16900
73360 93459 134689
5376 22401 49
42757 85879 196
44398 75312 683929
8638...

output:

33519157325

result:

ok single line: '33519157325'

Test #19:

score: 0
Accepted
time: 33ms
memory: 15652kb

input:

100000
1435 72992 229649
77103 85662 649117
58730 69709 863886
61447 86253 876313
74565 76572 472830
44107 79393 350500
41137 52613 527728
538 63056 38438
20646 44647 290139
61891 76883 753351
6072 25875 568962
19771 84275 845424
2442 93094 811923
34767 96668 114073
9047 70009 589869
52583 79007 473...

output:

40923129513

result:

ok single line: '40923129513'

Test #20:

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

input:

100000
20685 96916 128
12589 78172 2
75907 98043 32768
33412 43599 256
28402 56311 4
75057 95164 256
18859 65881 32
58435 69445 16
31713 70634 32
11894 34490 2
32679 92889 128
21672 42918 2048
8320 80109 524288
34664 83413 8
18994 75393 16384
4307 57235 4096
2698 66794 64
11639 73609 32
46199 49613 ...

output:

5208534241

result:

ok single line: '5208534241'

Test #21:

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

input:

100000
29790 44877 1
20821 59377 1
55745 84728 4
11367 15660 3
28976 31989 4
58327 65311 1
65892 92675 2
14945 15154 2
17270 26739 2
83250 98586 4
36053 60506 3
99246 99806 3
12554 60263 3
25925 87364 3
18116 49342 2
24039 68308 4
77124 88692 2
82787 83779 3
75447 97712 1
4120 74022 4
9288 37291 1
1...

output:

226715

result:

ok single line: '226715'

Test #22:

score: 0
Accepted
time: 31ms
memory: 13468kb

input:

100000
4455 27566 1000
23746 71495 1000
29071 72866 1000
12715 74588 1000
8688 38013 1
34339 41405 1
48162 77661 1000
19945 97278 1
4526 36040 1000
11339 84568 1
9811 71783 1
131 817 1
83995 87342 1000
23519 48915 1000
4852 84044 1
82866 98630 1000
56381 85284 1000
3535 72713 1
10662 51651 1
18761 5...

output:

50176869

result:

ok single line: '50176869'

Test #23:

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

input:

100000
14669 67533 121393
8294 79125 8
26634 29044 28657
52032 89041 8
15708 38350 17711
5151 69639 89
9063 67823 10946
65192 89707 5
43150 85884 10946
22611 52275 832040
6638 80299 8
64609 77915 121393
2999 89725 1
58389 92974 89
35612 54581 8
52114 69485 987
31539 36597 2584
3230 50809 3
68663 807...

output:

7267156024

result:

ok single line: '7267156024'

Test #24:

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

input:

100000
18499 20763 611793
55182 70329 893560
29145 52057 24779
14060 86844 288988
23121 84841 313862
72691 90290 65531
31437 90623 181055
14060 91228 658950
23121 76007 921026
10570 98970 510279
71615 82672 8075
68376 79045 846012
62742 77868 532973
69992 78619 67876
62742 85804 932955
23590 51775 4...

output:

49871404747

result:

ok single line: '49871404747'

Test #25:

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

input:

6
1 2 50
2 3 101
2 4 50
3 5 50
3 6 50

output:

201

result:

ok single line: '201'

Test #26:

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

input:

100000
57746 81588 4
2780 37342 32768
71597 79729 32768
51758 69352 16384
72301 74086 1
48520 55672 65536
15323 17947 131072
19651 99591 2
64165 90691 16
52184 73715 4
63185 65102 512
16270 46844 16384
28008 53648 16
56217 70645 2048
21725 98842 524288
27082 73610 131072
3899 4158 16384
72542 77556 ...

output:

5190141617

result:

ok single line: '5190141617'

Test #27:

score: 0
Accepted
time: 31ms
memory: 12064kb

input:

100000
74848 79598 196418
52197 52842 233
16439 55357 13
60831 64846 17711
14323 85256 377
29645 65887 5
15593 52815 987
71161 82306 89
19352 42519 46368
88817 89743 6765
72071 78257 377
43119 81019 10946
27764 66103 3
61181 80068 6765
4745 23880 3
41581 90325 2
37345 60580 55
18898 83811 1
6066 956...

output:

7296467200

result:

ok single line: '7296467200'

Test #28:

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

input:

100000
59002 65537 490136
37434 96703 552289
35264 50045 348679
13993 64539 486520
173 30076 70971
16037 75701 785025
46410 89048 449400
66311 94010 546391
19799 44445 588957
13864 41463 88544
74944 80213 368249
26357 76291 724595
30680 36524 54613
35122 65431 385179
65933 81668 947974
14727 92543 1...

output:

47198070966

result:

ok single line: '47198070966'

Test #29:

score: 0
Accepted
time: 31ms
memory: 10916kb

input:

99999
31285 50275 415349
77682 94037 803176
41716 58393 471366
22444 34453 850450
10979 44790 116191
68964 77882 338409
28259 49988 855920
3995 45835 693087
20561 48056 646082
29967 70259 795727
18106 94464 518012
73366 82976 896270
18239 46174 811907
3412 97762 316826
41145 49988 772696
49072 54113...

output:

50092334937

result:

ok single line: '50092334937'

Test #30:

score: 0
Accepted
time: 31ms
memory: 10840kb

input:

99999
11828 22169 753185
4168 20997 376735
11499 23488 53354
42358 99524 382124
13888 96248 745890
42358 82588 186614
91989 92861 445444
35667 58163 335751
43106 67819 622483
14148 68420 127636
20865 22580 811309
7419 8306 74820
59106 80818 583360
61417 67984 27736
6359 62471 297345
5623 98985 99442...

output:

50089457929

result:

ok single line: '50089457929'

Test #31:

score: 0
Accepted
time: 32ms
memory: 11516kb

input:

99991
28479 89549 1
47308 60831 32
68622 97330 4
54605 79229 4
22626 80464 4
19095 20224 512
32643 36283 65536
77295 92415 8192
48218 52532 64
57690 83500 2
40753 95075 8
39131 88044 1
42180 80848 1024
53172 84727 16
11158 76858 16
6842 8718 64
62111 66533 4096
28036 55787 32
9536 55945 8
16953 9960...

output:

5199837526

result:

ok single line: '5199837526'

Test #32:

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

input:

100000
60119 78407 96807
8154 98525 816637
23652 85785 42554
27906 28080 581640
8334 27607 286466
31345 40527 744124
12948 63022 154432
56128 58501 278870
77046 87910 658745
11102 38180 311150
20080 81893 545135
8349 22352 720024
873 85248 202951
204 69007 451572
19758 87870 905958
17193 62404 54598...

output:

45727161084

result:

ok single line: '45727161084'

Test #33:

score: 0
Accepted
time: 32ms
memory: 11348kb

input:

100000
51117 61908 5
32696 44854 5
47563 61417 5
5861 93637 5
11505 94046 5
24012 61565 5
20125 52596 5
74596 89873 5
41749 86528 5
56296 63815 5
42295 65980 5
23636 38888 5
44279 85004 5
64378 98755 5
30295 93317 5
27940 68354 5
34724 51122 5
45870 97966 5
7426 29553 5
64913 77998 5
12532 39264 5
6...

output:

438120

result:

ok single line: '438120'

Test #34:

score: 0
Accepted
time: 33ms
memory: 11288kb

input:

100000
14526 36165 16
60367 91453 32768
81680 85359 1
6966 70733 512
44266 69693 16384
71083 78552 16
35809 89111 128
78460 81230 1024
5999 48817 16
47726 54934 4
49927 89665 16
17578 39540 16
3003 93812 32768
19721 41405 64
35723 82978 8192
7052 86040 2
39114 73430 262144
13952 74165 32768
362 1755...

output:

5215444011

result:

ok single line: '5215444011'

Test #35:

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

input:

71163
31767 61872 674041
9487 39660 616225
8751 50202 86436
23788 51699 935089
16693 18996 872356
38209 55291 289
17690 65743 26244
40630 45080 8836
37085 50744 45369
3594 45879 763876
6285 69930 857476
15517 29587 315844
12790 54627 779689
38320 58517 101124
33498 66958 900
12637 40474 580644
45629...

output:

22396307131

result:

ok single line: '22396307131'

Test #36:

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

input:

50000
29294 31889 358467
14510 31889 207371
31889 43245 117080
31889 39695 765375
31889 33043 553667
13266 31889 115686
30950 31889 430500
2588 31889 800291
31889 39909 121576
5365 31889 960651
3622 31889 484990
31889 36218 587949
7059 31889 959383
31889 35370 929739
2911 31889 896255
20165 31889 90...

output:

24939402335

result:

ok single line: '24939402335'

Test #37:

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

input:

90753
44346 67512 2
45150 76797 17711
40361 73678 4181
32889 60914 3
70745 72266 13
4872 52666 28657
65650 70060 13
49401 61452 2584
190 81663 5
1740 18132 1
5736 66066 196418
386 32644 5
20384 28033 89
40138 74265 4181
25707 78855 10946
75563 84850 4181
9782 65127 28657
56939 88688 832040
5201 4182...

output:

6626906568

result:

ok single line: '6626906568'

Test #38:

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

input:

100000
10794 57640 53329
27843 85391 982932
54855 74281 601607
6728 55725 706815
43069 66018 210101
70209 91863 42311
75904 98930 298023
59019 73349 262890
27752 29381 574243
20973 55136 304890
13254 27401 693315
61359 63249 73522
76786 93302 899427
1554 80771 496922
27011 91778 839318
73872 97919 8...

output:

45542882272

result:

ok single line: '45542882272'

Test #39:

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

input:

100000
59463 98763 5
17640 57336 5
4980 15955 5
21900 47824 5
5336 76608 5
14313 23952 5
37059 99009 5
29137 35807 5
44016 56777 5
54715 95849 5
40163 51223 5
77449 77579 5
7564 84541 5
53187 84606 5
29466 59341 5
57856 79425 5
759 43921 5
28635 99571 5
73583 76028 5
3719 15005 5
6649 7055 5
37234 4...

output:

438555

result:

ok single line: '438555'

Test #40:

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

input:

100000
5136 85605 65536
6023 71166 4096
21757 65834 512
42882 95156 256
32581 43914 32
7693 17652 16384
58485 94513 32768
5285 53432 2048
52977 68478 4
9899 15047 131072
41958 59097 1024
22201 87636 1
60629 73485 4
44714 96712 65536
15067 39929 131072
2642 44096 524288
29500 62273 32
4486 92657 5242...

output:

5193439872

result:

ok single line: '5193439872'

Test #41:

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

input:

83128
59537 70048 39601
17664 74866 339889
38010 71889 285156
21996 59519 258064
16844 68030 1369
7456 54192 238144
53721 76846 537289
45624 53753 277729
47928 61834 68121
21977 75786 228484
3544 59650 40000
59 69354 5625
27678 34052 81
1842 33832 531441
4419 7752 44521
62622 68295 25600
3424 41868 ...

output:

26118539499

result:

ok single line: '26118539499'

Test #42:

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

input:

63326
19170 30643 233
11736 32584 55
12283 50502 10946
127 33839 34
16510 58814 75025
37972 50322 144
27656 46356 514229
6278 31799 55
23302 59413 28657
20324 41441 233
12816 58514 21
5346 42824 1
1742 32931 17711
20068 20766 8
49758 52177 5
18552 48223 610
3702 62734 6765
1169 38586 196418
40188 56...

output:

4656200176

result:

ok single line: '4656200176'

Test #43:

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

input:

100000
6812 21703 823613
12391 99004 955433
43573 66978 673201
52083 87935 237660
5557 81935 79616
52316 70602 793881
28873 80391 291540
36903 53245 791926
5213 28794 139665
39983 97389 707423
56369 59641 663007
1996 88359 497609
16917 87936 412846
22269 30396 782428
32415 77061 140017
29422 91495 9...

output:

45694419089

result:

ok single line: '45694419089'

Test #44:

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

input:

100000
39757 87314 5
33046 75755 5
19715 68257 5
9881 38974 5
22906 53482 5
7687 33523 5
15897 18754 5
4963 88218 5
4092 62843 5
21367 87851 5
21012 88904 5
33808 74967 5
26640 70364 5
82650 85999 5
2261 38193 5
23405 31938 5
37691 79570 5
19226 31932 5
9335 68647 5
38888 90949 5
6854 62807 5
24721 ...

output:

438910

result:

ok single line: '438910'

Test #45:

score: 0
Accepted
time: 31ms
memory: 11228kb

input:

100000
34461 83545 2
44033 89661 262144
129 76248 8
17090 27275 65536
37646 97386 16
32999 92845 8192
5388 50974 32
55876 91405 131072
90719 91964 131072
12539 18520 128
31438 37184 4096
47963 85334 4096
5600 27655 32768
24623 41615 2048
33293 51186 16384
62198 84179 262144
46184 83377 1
3812 20829 ...

output:

5180706354

result:

ok single line: '5180706354'

Test #46:

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

input:

85782
43938 73138 379456
18559 70345 47524
62930 77490 567009
18330 60844 660969
80612 81563 330625
12259 16246 786769
17244 35577 2304
61604 77090 461041
12258 45428 3364
20920 35180 101761
39037 68292 136900
3447 13978 358801
8746 23510 12544
47228 80803 45369
23034 24772 9216
29017 34825 326041
7...

output:

26862047009

result:

ok single line: '26862047009'

Test #47:

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

input:

50001
10401 41397 480547
13987 41397 881393
14973 41397 936882
21644 41397 318809
32390 41397 620098
8964 41397 521272
1600 41397 910399
39221 41397 488298
31382 41397 888847
25177 41397 90624
5306 41397 692399
40565 41397 163559
11799 41397 700861
10513 41397 67786
37101 41397 904985
34215 41397 22...

output:

24928367536

result:

ok single line: '24928367536'

Test #48:

score: 0
Accepted
time: 35ms
memory: 10992kb

input:

94140
16201 27114 1597
61505 78183 75025
43809 86558 121393
13137 61815 55
14596 48537 832040
50350 66158 34
82343 93562 5
9235 77256 13
7349 53091 28657
10137 87821 28657
69317 89848 2
28800 49126 832040
15529 90509 4181
16163 90305 17711
24765 51564 144
2929 90632 13
1378 49458 2584
1177 22046 89
...

output:

6768090506

result:

ok single line: '6768090506'

Test #49:

score: 0
Accepted
time: 32ms
memory: 15896kb

input:

100000
30147 57386 1000000
34404 60249 1000000
55703 99927 1000000
16145 51364 1000000
69924 94737 1000000
36701 38107 1000000
10507 26987 1000000
87040 98518 1000000
17262 82190 1000000
18857 35513 1000000
33217 58579 1000000
55025 73166 1000000
3532 66696 1000000
13049 58782 1000000
14348 95718 10...

output:

99999000000

result:

ok single line: '99999000000'

Test #50:

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

input:

99996
29224 74267 434082
51081 75579 515738
9931 81446 313277
32928 80821 917799
57745 96723 410832
6206 66735 703239
909 53328 1864
25567 44458 194913
25239 32048 98068
879 6943 222859
1870 57077 938419
56 45457 243079
40051 52960 77360
5512 69487 87012
6049 43660 872017
9668 64840 343539
46612 594...

output:

40345347947

result:

ok single line: '40345347947'

Test #51:

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

input:

99990
12443 28747 128
21844 84411 32
26325 54512 4
41174 71506 65536
27952 69390 8
48082 70412 16
61173 69721 131072
55314 87749 32768
6161 8901 1024
53383 96951 16384
45417 82298 1
18771 97518 65536
43430 60714 262144
36774 64130 16
8364 40700 1024
81886 87506 64
1176 91051 16384
62130 81953 2048
2...

output:

5079038074

result:

ok single line: '5079038074'

Test #52:

score: 0
Accepted
time: 38ms
memory: 11844kb

input:

99990
11747 85466 2
1488 83589 2
47856 74972 55
42673 92978 144
35547 74074 5
14663 80577 121393
6443 18290 1597
31783 46125 8
3957 24321 8
40302 73115 17711
84314 85297 89
56885 61469 1
22961 90056 2584
1471 29492 89
42810 97261 121393
60108 88172 13
54690 92944 13
34977 94778 196418
58308 70511 1
...

output:

7105815458

result:

ok single line: '7105815458'