QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#544422#8256. Construction Project 2ZhaoZiLong100 ✓304ms166788kbC++172.0kb2024-09-02 16:26:392024-09-02 16:26:39

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 3ms
memory: 15016kb

input:

50 46
39 46 1 2
1 46 1
2 39 1
3 39 1
4 39 1
5 46 1
6 39 1
7 39 1
8 39 1
9 39 1
10 39 1
11 39 1
12 46 1
14 46 1
15 46 1
16 39 1
17 46 1
18 39 1
19 46 1
20 46 1
21 39 1
22 46 1
23 46 1
24 46 1
25 46 1
26 39 1
27 39 1
28 39 1
29 39 1
30 39 1
31 39 1
34 46 1
35 46 1
36 39 1
37 39 1
38 46 1
40 46 1
39 41...

output:

42

result:

ok single line: '42'

Test #2:

score: 8
Accepted
time: 2ms
memory: 15164kb

input:

50 44
26 33 1 2
1 33 1
2 26 1
5 26 1
6 33 1
7 26 1
8 26 1
9 26 1
10 26 1
11 26 1
12 26 1
13 33 1
14 33 1
17 33 1
19 33 1
20 33 1
22 26 1
23 26 1
24 33 1
25 33 1
26 27 1
29 33 1
31 33 1
33 34 1
33 35 1
33 36 1
33 37 1
33 38 1
26 39 1
33 40 1
33 41 1
33 42 1
26 44 1
26 46 1
26 47 1
33 48 1
26 49 1
33 ...

output:

38

result:

ok single line: '38'

Test #3:

score: 8
Accepted
time: 3ms
memory: 16208kb

input:

3000 2419
1360 1389 1 2
1 1360 1
2 1360 1
3 1360 1
4 1389 1
5 1389 1
6 1389 1
7 1389 1
8 1360 1
9 1360 1
10 1360 1
11 1389 1
12 1360 1
13 1360 1
14 1389 1
15 1389 1
16 1389 1
18 1360 1
19 1360 1
20 1360 1
21 1360 1
22 1389 1
23 1360 1
24 1360 1
25 1389 1
26 1389 1
27 1360 1
28 1389 1
29 1360 1
30 13...

output:

2414

result:

ok single line: '2414'

Test #4:

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

input:

3000 2426
30 2955 1 2
1 2955 1
2 2955 1
3 2955 1
4 30 1
5 30 1
6 30 1
7 2955 1
8 30 1
10 2955 1
11 2955 1
12 30 1
13 30 1
15 2955 1
16 2955 1
17 30 1
18 30 1
19 2955 1
20 2955 1
21 2955 1
22 30 1
23 30 1
25 2955 1
26 2955 1
27 2955 1
28 2955 1
29 30 1
31 2955 1
30 32 1
34 2955 1
30 35 1
36 2955 1
30...

output:

4498500

result:

ok single line: '4498500'

Test #5:

score: 8
Accepted
time: 73ms
memory: 24616kb

input:

200000 160037
88185 132270 1 2
1 132270 1
3 132270 1
5 132270 1
6 88185 1
8 88185 1
9 88185 1
10 132270 1
11 132270 1
13 132270 1
16 132270 1
17 88185 1
18 88185 1
20 88185 1
21 132270 1
22 132270 1
23 132270 1
24 132270 1
25 88185 1
26 132270 1
27 132270 1
28 88185 1
29 132270 1
31 88185 1
32 88185...

output:

160035

result:

ok single line: '160035'

Test #6:

score: 8
Accepted
time: 78ms
memory: 24816kb

input:

200000 159789
156039 195320 1 2
3 195320 1
4 156039 1
6 156039 1
8 195320 1
10 195320 1
12 156039 1
13 195320 1
14 195320 1
15 195320 1
17 156039 1
20 195320 1
22 195320 1
23 156039 1
24 195320 1
27 156039 1
28 195320 1
29 195320 1
30 195320 1
31 195320 1
32 156039 1
33 195320 1
34 195320 1
35 19532...

output:

159786

result:

ok single line: '159786'

Test #7:

score: 8
Accepted
time: 45ms
memory: 27352kb

input:

200000 159948
96296 139890 1 2
1 139890 1
2 139890 1
3 139890 1
4 96296 1
5 139890 1
6 139890 1
7 139890 1
8 139890 1
9 96296 1
10 96296 1
11 96296 1
12 139890 1
14 96296 1
15 139890 1
16 96296 1
18 96296 1
20 96296 1
21 139890 1
24 139890 1
26 139890 1
27 139890 1
28 96296 1
29 96296 1
30 139890 1
...

output:

19999900000

result:

ok single line: '19999900000'

Test #8:

score: 8
Accepted
time: 3ms
memory: 15208kb

input:

50 25
8 15 1 2
39 40 1
11 26 1
4 27 1
7 29 1
12 24 1
27 42 1
26 49 1
27 35 1
31 39 1
15 37 1
9 30 1
3 23 1
10 43 1
2 9 1
8 12 1
6 27 1
35 36 1
25 50 1
41 47 1
18 27 1
15 31 1
5 6 1
3 25 1
38 49 1
1 37 1

output:

4

result:

ok single line: '4'

Test #9:

score: 8
Accepted
time: 2ms
memory: 14092kb

input:

50 50
33 37 1 2
32 50 1
12 14 1
4 11 1
12 42 1
44 48 1
21 46 1
14 36 1
20 34 1
10 50 1
5 45 1
10 36 1
13 32 1
9 29 1
14 21 1
14 42 1
10 39 1
34 47 1
3 22 1
16 39 1
9 49 1
7 27 1
1 11 1
23 29 1
18 23 1
22 48 1
14 32 1
28 32 1
10 24 1
2 4 1
11 15 1
37 44 1
22 46 1
3 33 1
35 50 1
14 19 1
19 43 1
23 37 ...

output:

5

result:

ok single line: '5'

Test #10:

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

input:

3000 1500
424 1182 1 2
2126 2364 1
1664 2582 1
2252 2664 1
80 2286 1
148 2474 1
658 812 1
739 2183 1
144 180 1
319 2084 1
805 1528 1
821 1049 1
439 1404 1
712 1397 1
193 2507 1
122 2957 1
1385 1844 1
1034 2527 1
113 567 1
521 2162 1
498 2042 1
1613 1947 1
2013 2743 1
2314 2697 1
2779 2898 1
205 2098...

output:

3

result:

ok single line: '3'

Test #11:

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

input:

3000 3000
1698 2777 1 2
1065 2115 1
1167 2496 1
694 2313 1
1379 1868 1
223 770 1
1970 2119 1
289 537 1
1194 2859 1
72 1064 1
2583 2883 1
1211 2103 1
622 1748 1
649 1532 1
1221 2083 1
767 1718 1
2239 2810 1
304 1889 1
1048 2729 1
92 322 1
584 2918 1
42 1998 1
160 542 1
866 1248 1
1829 2324 1
611 1443...

output:

4

result:

ok single line: '4'

Test #12:

score: 8
Accepted
time: 54ms
memory: 21528kb

input:

200000 100000
46706 69791 1 2
151808 156313 1
28022 37489 1
76906 125687 1
7808 163773 1
91420 174488 1
11314 168440 1
66409 168233 1
166631 173716 1
43439 101663 1
97615 162798 1
31889 169824 1
17638 194343 1
172947 192186 1
120411 196358 1
84695 196401 1
185433 198102 1
76328 85703 1
34215 159517 ...

output:

2

result:

ok single line: '2'

Test #13:

score: 8
Accepted
time: 123ms
memory: 26960kb

input:

200000 200000
108109 162827 1 2
49484 110100 1
2650 19925 1
195272 199535 1
192970 197399 1
9574 91823 1
91433 103939 1
25666 190641 1
82404 194272 1
7984 131610 1
112543 199959 1
25177 97169 1
145319 171345 1
126654 131029 1
106315 193835 1
117374 135540 1
17675 41269 1
18895 88212 1
102310 184232 ...

output:

5

result:

ok single line: '5'

Test #14:

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

input:

50 49
29 50 1 2
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 38 1
38 39...

output:

4

result:

ok single line: '4'

Test #15:

score: 8
Accepted
time: 4ms
memory: 15100kb

input:

3000 2999
106 340 1 2
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 38 1...

output:

5

result:

ok single line: '5'

Test #16:

score: 8
Accepted
time: 80ms
memory: 28632kb

input:

200000 199999
88906 117336 1 2
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 ...

output:

5

result:

ok single line: '5'

Test #17:

score: 8
Accepted
time: 3ms
memory: 14836kb

input:

50 25
8 15 1 2
39 40 1
11 26 1
4 27 1
7 29 1
12 24 1
27 42 1
26 49 1
27 35 1
31 39 1
15 37 1
9 30 1
3 23 1
10 43 1
2 9 1
8 12 1
6 27 1
35 36 1
25 50 1
41 47 1
18 27 1
15 31 1
5 6 1
3 25 1
38 49 1
1 37 1

output:

4

result:

ok single line: '4'

Test #18:

score: 8
Accepted
time: 2ms
memory: 15936kb

input:

50 50
33 37 1 2
32 50 1
12 14 1
4 11 1
12 42 1
44 48 1
21 46 1
14 36 1
20 34 1
10 50 1
5 45 1
10 36 1
13 32 1
9 29 1
14 21 1
14 42 1
10 39 1
34 47 1
3 22 1
16 39 1
9 49 1
7 27 1
1 11 1
23 29 1
18 23 1
22 48 1
14 32 1
28 32 1
10 24 1
2 4 1
11 15 1
37 44 1
22 46 1
3 33 1
35 50 1
14 19 1
19 43 1
23 37 ...

output:

5

result:

ok single line: '5'

Test #19:

score: 8
Accepted
time: 3ms
memory: 15412kb

input:

3000 1500
424 1182 1 2
2126 2364 1
1664 2582 1
2252 2664 1
80 2286 1
148 2474 1
658 812 1
739 2183 1
144 180 1
319 2084 1
805 1528 1
821 1049 1
439 1404 1
712 1397 1
193 2507 1
122 2957 1
1385 1844 1
1034 2527 1
113 567 1
521 2162 1
498 2042 1
1613 1947 1
2013 2743 1
2314 2697 1
2779 2898 1
205 2098...

output:

3

result:

ok single line: '3'

Test #20:

score: 8
Accepted
time: 3ms
memory: 14676kb

input:

3000 3000
1698 2777 1 2
1065 2115 1
1167 2496 1
694 2313 1
1379 1868 1
223 770 1
1970 2119 1
289 537 1
1194 2859 1
72 1064 1
2583 2883 1
1211 2103 1
622 1748 1
649 1532 1
1221 2083 1
767 1718 1
2239 2810 1
304 1889 1
1048 2729 1
92 322 1
584 2918 1
42 1998 1
160 542 1
866 1248 1
1829 2324 1
611 1443...

output:

4

result:

ok single line: '4'

Test #21:

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

input:

200000 100000
46706 69791 1 2
151808 156313 1
28022 37489 1
76906 125687 1
7808 163773 1
91420 174488 1
11314 168440 1
66409 168233 1
166631 173716 1
43439 101663 1
97615 162798 1
31889 169824 1
17638 194343 1
172947 192186 1
120411 196358 1
84695 196401 1
185433 198102 1
76328 85703 1
34215 159517 ...

output:

2

result:

ok single line: '2'

Test #22:

score: 8
Accepted
time: 107ms
memory: 26932kb

input:

200000 200000
108109 162827 1 2
49484 110100 1
2650 19925 1
195272 199535 1
192970 197399 1
9574 91823 1
91433 103939 1
25666 190641 1
82404 194272 1
7984 131610 1
112543 199959 1
25177 97169 1
145319 171345 1
126654 131029 1
106315 193835 1
117374 135540 1
17675 41269 1
18895 88212 1
102310 184232 ...

output:

5

result:

ok single line: '5'

Test #23:

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

input:

50 49
18 22 1 2
1 18 1
2 18 1
3 18 1
4 18 1
5 18 1
6 18 1
7 18 1
8 18 1
9 18 1
10 18 1
11 18 1
12 18 1
13 18 1
14 18 1
15 18 1
16 18 1
17 18 1
18 19 1
18 20 1
18 21 1
18 22 1
18 23 1
18 24 1
18 25 1
18 26 1
18 27 1
18 28 1
18 29 1
18 30 1
18 31 1
18 32 1
18 33 1
18 34 1
18 35 1
18 36 1
18 37 1
18 38...

output:

1225

result:

ok single line: '1225'

Test #24:

score: 8
Accepted
time: 2ms
memory: 10908kb

input:

3000 2999
595 1315 1 2
1 595 1
2 595 1
3 595 1
4 595 1
5 595 1
6 595 1
7 595 1
8 595 1
9 595 1
10 595 1
11 595 1
12 595 1
13 595 1
14 595 1
15 595 1
16 595 1
17 595 1
18 595 1
19 595 1
20 595 1
21 595 1
22 595 1
23 595 1
24 595 1
25 595 1
26 595 1
27 595 1
28 595 1
29 595 1
30 595 1
31 595 1
32 595 ...

output:

4498500

result:

ok single line: '4498500'

Test #25:

score: 8
Accepted
time: 39ms
memory: 30716kb

input:

200000 199999
103332 117336 1 2
1 174713 1
2 174713 1
3 174713 1
4 174713 1
5 174713 1
6 174713 1
7 174713 1
8 174713 1
9 174713 1
10 174713 1
11 174713 1
12 174713 1
13 174713 1
14 174713 1
15 174713 1
16 174713 1
17 174713 1
18 174713 1
19 174713 1
20 174713 1
21 174713 1
22 174713 1
23 174713 1
2...

output:

19999900000

result:

ok single line: '19999900000'

Test #26:

score: 8
Accepted
time: 48ms
memory: 24904kb

input:

100002 199998
1 100002 1 2
2 3 1
3 100001 1
2 4 1
4 100001 1
2 5 1
5 100001 1
2 6 1
6 100001 1
2 7 1
7 100001 1
2 8 1
8 100001 1
2 9 1
9 100001 1
2 10 1
10 100001 1
2 11 1
11 100001 1
2 12 1
12 100001 1
2 13 1
13 100001 1
2 14 1
14 100001 1
2 15 1
15 100001 1
2 16 1
16 100001 1
2 17 1
17 100001 1
2 ...

output:

3

result:

ok single line: '3'

Test #27:

score: 8
Accepted
time: 50ms
memory: 26892kb

input:

133333 199998
44154 63670 1 2
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1...

output:

9

result:

ok single line: '9'

Subtask #2:

score: 16
Accepted

Test #28:

score: 16
Accepted
time: 2ms
memory: 14260kb

input:

10 45
3 9 48001343 237852277
1 4 716247826
1 9 297456468
4 6 735727475
2 8 320343417
7 9 689896692
2 5 701067214
2 7 77422890
1 7 165861933
8 9 647608572
2 9 619230449
5 10 322773035
3 5 438584763
2 6 184583372
1 6 671713339
5 9 926450489
3 4 155266400
3 8 524274898
6 9 621438120
1 2 388629374
6 8 3...

output:

3

result:

ok single line: '3'

Test #29:

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

input:

50 25
28 31 517111554 4785421536
1 29 50881664
23 28 227292135
27 30 671954238
15 38 318924437
2 12 593515726
34 48 809321109
25 32 420432800
13 38 851093542
46 47 415426245
12 16 449037819
21 26 46799507
17 47 550171135
7 25 742117593
2 16 663763300
12 38 627639003
18 22 178724904
17 39 581167096
1...

output:

4

result:

ok single line: '4'

Test #30:

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

input:

50 50
35 37 202335917 1783119420
4 25 921403824
5 37 863628607
2 3 481462008
3 7 136648030
26 32 394170449
14 42 687142065
8 48 439408737
9 31 986589592
12 32 300012389
22 41 609774899
27 44 553941369
5 13 451110464
5 11 834488498
20 25 938624074
20 36 963261736
15 36 283215476
24 44 652058981
15 25...

output:

1225

result:

ok single line: '1225'

Test #31:

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

input:

50 50
3 16 226988118 931961588
3 29 60317431
24 45 40418630
31 33 206629327
11 14 569111082
17 19 529884319
34 36 128886324
13 23 286351330
5 12 813574559
10 40 186268235
29 37 754174858
36 47 771247261
20 24 275653822
31 49 860154492
23 37 338828277
13 39 228821838
17 29 71993788
6 33 120972460
48 ...

output:

20

result:

ok single line: '20'

Test #32:

score: 16
Accepted
time: 2ms
memory: 15004kb

input:

45 50
23 40 1 7265158065
3 23 117103728
15 35 205131281
30 41 5608977
17 31 646469662
13 31 439955161
10 25 546992253
21 27 924429614
22 29 459058431
22 44 342375130
35 42 744337772
16 39 823117757
11 39 453450429
19 40 800250952
35 37 989299285
8 41 387227075
24 40 419234993
18 32 307592927
10 37 4...

output:

802

result:

ok single line: '802'

Test #33:

score: 16
Accepted
time: 2ms
memory: 12668kb

input:

50 50
26 46 1 16474572356
2 9 678194444
42 48 631558289
1 25 212407978
24 49 55775748
8 13 514389450
19 20 486297511
6 27 142770345
7 22 561723213
42 44 58227125
12 18 568467392
34 38 862812064
4 17 660692501
7 23 339974629
34 43 385963771
46 47 459760428
10 31 339284104
19 40 666793010
13 32 843860...

output:

1069

result:

ok single line: '1069'

Test #34:

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

input:

50 49
1 37 62077031 8696776315
1 2 292522155
2 3 869840090
3 4 178094257
4 5 525073932
5 6 210458171
6 7 724541833
7 8 45171648
8 9 236436225
9 10 889545720
10 11 530973359
11 12 782755079
12 13 241386498
13 14 423300413
14 15 904101124
15 16 529285946
16 17 437362596
17 18 109246525
18 19 668702439...

output:

304

result:

ok single line: '304'

Test #35:

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

input:

50 49
2 44 568136495 10624401863
1 2 157405469
2 3 898172713
3 4 641565182
4 5 592223593
5 6 493808282
6 7 20317004
7 8 419298042
8 9 927082192
9 10 134095077
10 11 189996718
11 12 1255599
12 13 706502656
13 14 755414640
14 15 441555083
15 16 64428484
16 17 533395510
17 18 189797682
18 19 881414997
...

output:

417

result:

ok single line: '417'

Test #36:

score: 16
Accepted
time: 2ms
memory: 12664kb

input:

10 45
3 9 48001343 187948044
1 4 716247826
1 9 297456468
4 6 735727475
2 8 320343417
7 9 689896692
2 5 701067214
2 7 77422890
1 7 165861933
8 9 647608572
2 9 619230449
5 10 322773035
3 5 438584763
2 6 184583372
1 6 671713339
5 9 926450489
3 4 155266400
3 8 524274898
6 9 621438120
1 2 388629374
6 8 3...

output:

2

result:

ok single line: '2'

Test #37:

score: 16
Accepted
time: 2ms
memory: 12704kb

input:

50 25
28 31 517111554 792814785421536
1 29 50881664
23 28 227292135
27 30 671954238
15 38 318924437
2 12 593515726
34 48 809321109
25 32 420432800
13 38 851093542
46 47 415426245
12 16 449037819
21 26 46799507
17 47 550171135
7 25 742117593
2 16 663763300
12 38 627639003
18 22 178724904
17 39 581167...

output:

4

result:

ok single line: '4'

Test #38:

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

input:

50 50
35 37 202335917 1093895627
4 25 921403824
5 37 863628607
2 3 481462008
3 7 136648030
26 32 394170449
14 42 687142065
8 48 439408737
9 31 986589592
12 32 300012389
22 41 609774899
27 44 553941369
5 13 451110464
5 11 834488498
20 25 938624074
20 36 963261736
15 36 283215476
24 44 652058981
15 25...

output:

6

result:

ok single line: '6'

Test #39:

score: 16
Accepted
time: 2ms
memory: 15024kb

input:

50 50
3 16 226988118 831720149938959
3 29 60317431
24 45 40418630
31 33 206629327
11 14 569111082
17 19 529884319
34 36 128886324
13 23 286351330
5 12 813574559
10 40 186268235
29 37 754174858
36 47 771247261
20 24 275653822
31 49 860154492
23 37 338828277
13 39 228821838
17 29 71993788
6 33 1209724...

output:

41

result:

ok single line: '41'

Test #40:

score: 16
Accepted
time: 2ms
memory: 15600kb

input:

50 49
22 31 326576217 893777453
1 5 869840090
2 5 178094257
3 5 525073932
4 5 210458171
5 6 724541833
5 7 45171648
5 8 236436225
5 9 889545720
5 10 530973359
5 11 782755079
5 12 241386498
5 13 423300413
5 14 904101124
5 15 529285946
5 16 437362596
5 17 109246525
5 18 668702439
5 19 410617561
5 20 97...

output:

9

result:

ok single line: '9'

Test #41:

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

input:

50 49
2 45 87438492 617116363
1 19 898172713
2 19 641565182
3 19 592223593
4 19 493808282
5 19 20317004
6 19 419298042
7 19 927082192
8 19 134095077
9 19 189996718
10 19 1255599
11 19 706502656
12 19 755414640
13 19 441555083
14 19 64428484
15 19 533395510
16 19 189797682
17 19 881414997
18 19 85131...

output:

10

result:

ok single line: '10'

Test #42:

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

input:

27 48
1 27 291537623 291537625
2 3 2
3 26 999999994
2 4 3
4 26 999999992
2 5 4
5 26 999999990
2 6 5
6 26 999999988
2 7 6
7 26 999999986
2 8 7
8 26 999999984
2 9 8
9 26 999999982
2 10 9
10 26 999999980
2 11 10
11 26 999999978
2 12 11
12 26 999999976
2 13 12
13 26 999999974
2 14 13
14 26 999999972
2 1...

output:

4

result:

ok single line: '4'

Test #43:

score: 16
Accepted
time: 2ms
memory: 15256kb

input:

27 48
1 27 290846782 290846785
2 3 2
3 26 999999994
2 4 3
4 26 999999992
2 5 4
5 26 999999990
2 6 5
6 26 999999988
2 7 6
7 26 999999986
2 8 7
8 26 999999984
2 9 8
9 26 999999982
2 10 9
10 26 999999980
2 11 10
11 26 999999978
2 12 11
12 26 999999976
2 13 12
13 26 999999974
2 14 13
14 26 999999972
2 1...

output:

5

result:

ok single line: '5'

Test #44:

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

input:

33 48
1 13 8 21
1 2 3
2 3 4
3 4 6
4 5 10
5 6 18
6 7 34
7 8 66
8 9 130
9 10 258
10 11 514
11 12 1026
12 13 2050
13 14 4098
14 15 8194
15 16 16386
16 17 32770
1 18 1
2 18 1
2 19 1
3 19 1
3 20 1
4 20 1
4 21 1
5 21 1
5 22 1
6 22 1
6 23 1
7 23 1
7 24 1
8 24 1
8 25 1
9 25 1
9 26 1
10 26 1
10 27 1
11 27 1
...

output:

181

result:

ok single line: '181'

Test #45:

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

input:

33 48
20 23 2 5
1 2 3
2 3 4
3 4 6
4 5 10
5 6 18
6 7 34
7 8 66
8 9 130
9 10 258
10 11 514
11 12 1026
12 13 2050
13 14 4098
14 15 8194
15 16 16386
16 17 32770
1 18 1
2 18 1
2 19 1
3 19 1
3 20 1
4 20 1
4 21 1
5 21 1
5 22 1
6 22 1
6 23 1
7 23 1
7 24 1
8 24 1
8 25 1
9 25 1
9 26 1
10 26 1
10 27 1
11 27 1
...

output:

25

result:

ok single line: '25'

Test #46:

score: 16
Accepted
time: 2ms
memory: 13140kb

input:

4 3
1 4 8 19
1 2 5
2 3 6
3 4 7

output:

6

result:

ok single line: '6'

Test #47:

score: 16
Accepted
time: 2ms
memory: 13892kb

input:

37 50
3 13 800000000 1486504444
13 15 370585303
1 22 512800722
14 27 106885266
10 16 725594291
30 36 108956774
19 36 433628006
1 12 545984301
27 35 189360159
12 16 664402534
11 12 380504104
1 8 45728948
13 28 515146903
1 32 940614835
17 25 645491830
9 29 807839266
8 34 332046289
13 34 338976005
18 2...

output:

666

result:

ok single line: '666'

Subtask #3:

score: 29
Accepted

Dependency #2:

100%
Accepted

Test #48:

score: 29
Accepted
time: 2ms
memory: 10844kb

input:

77 2926
15 52 27443170 55437463
40 66 884970624
46 62 148260852
5 67 711213444
37 57 407386525
3 73 782822297
15 24 993934552
2 14 894478216
45 49 950454850
15 62 211244372
57 58 748597691
31 53 528827244
21 63 162292047
35 39 8468495
6 17 772380575
11 23 826919554
4 33 795485582
48 77 951290021
1 5...

output:

2926

result:

ok single line: '2926'

Test #49:

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

input:

3000 1500
1585 2733 853417396 31014668872
205 2294 677175644
315 1437 460335775
2677 2747 966733810
1927 2729 282640164
1549 1836 111230221
1099 1101 337219213
1483 1561 444444957
2072 2797 796173172
1802 2659 336835010
1190 1555 82345077
1492 2715 924926863
1406 1629 399624633
370 412 537502164
206...

output:

1

result:

ok single line: '1'

Test #50:

score: 29
Accepted
time: 2ms
memory: 15400kb

input:

3000 3000
10 903 639468436 4812743596
227 1344 926811751
1919 1949 837083439
228 638 141284653
2137 2481 840777783
667 885 983425115
527 2975 541524579
1937 2752 777540325
48 1745 951895032
1146 2285 865318421
247 2247 524068937
347 2846 407037626
1074 2949 229857419
611 1217 169780190
1810 2031 604...

output:

4303

result:

ok single line: '4303'

Test #51:

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

input:

3000 3000
1141 2362 235601608 29034840309
1741 2548 75242545
868 1358 157029860
708 1793 182150282
571 2794 648800173
100 1815 496177778
2174 2439 738541998
1962 2024 882029519
1031 1853 773454049
1215 1644 424709187
1946 2763 479842947
683 2326 461077188
2487 2608 781511670
1497 2455 390810057
1034...

output:

2376

result:

ok single line: '2376'

Test #52:

score: 29
Accepted
time: 5ms
memory: 13672kb

input:

2950 3000
151 2265 1 70014788174
164 2476 707887851
1632 1726 595040900
392 659 904043903
1915 1924 789052293
604 2109 374673225
1053 1779 686551750
914 2920 64920893
337 574 468348212
148 186 873307341
295 2310 89340476
209 682 90871431
113 2174 87826441
817 2025 365339356
1597 1907 399842642
1972 ...

output:

473752

result:

ok single line: '473752'

Test #53:

score: 29
Accepted
time: 5ms
memory: 13868kb

input:

3000 3000
2320 2570 1 680489405665
1015 2002 860672629
1417 1713 901417954
1322 2833 906064194
1982 2390 783831242
1530 1601 309730179
1256 1316 592667195
1121 1855 830334998
1188 2494 400513385
446 1770 170304589
477 2022 639234245
337 2902 225422866
330 2036 271553221
659 776 293406851
395 2757 21...

output:

2540588

result:

ok single line: '2540588'

Test #54:

score: 29
Accepted
time: 4ms
memory: 13832kb

input:

3000 2999
1425 2355 595313768 232333375519
1 2 23740312
2 3 868240697
3 4 678422653
4 5 470112241
5 6 287865697
6 7 795471532
7 8 515973225
8 9 676155032
9 10 129913532
10 11 512705401
11 12 156951202
12 13 260465388
13 14 852576523
14 15 472285618
15 16 275211045
16 17 382241208
17 18 457235581
18 ...

output:

429106

result:

ok single line: '429106'

Test #55:

score: 29
Accepted
time: 4ms
memory: 13968kb

input:

3000 2999
24 630 489717827 152590938397
1 2 156023787
2 3 632369519
3 4 599104976
4 5 547934290
5 6 213249600
6 7 367076117
7 8 594980655
8 9 428235794
9 10 94512657
10 11 574535841
11 12 4815945
12 13 404101641
13 14 828498741
14 15 149032176
15 16 43195102
16 17 49501417
17 18 71553666
18 19 56386...

output:

102293

result:

ok single line: '102293'

Test #56:

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

input:

77 2926
15 52 27443170 55161901
40 66 884970624
46 62 148260852
5 67 711213444
37 57 407386525
3 73 782822297
15 24 993934552
2 14 894478216
45 49 950454850
15 62 211244372
57 58 748597691
31 53 528827244
21 63 162292047
35 39 8468495
6 17 772380575
11 23 826919554
4 33 795485582
48 77 951290021
1 5...

output:

34

result:

ok single line: '34'

Test #57:

score: 29
Accepted
time: 2ms
memory: 12580kb

input:

3000 1500
1585 2733 853417396 913559014668872
205 2294 677175644
315 1437 460335775
2677 2747 966733810
1927 2729 282640164
1549 1836 111230221
1099 1101 337219213
1483 1561 444444957
2072 2797 796173172
1802 2659 336835010
1190 1555 82345077
1492 2715 924926863
1406 1629 399624633
370 412 537502164...

output:

1

result:

ok single line: '1'

Test #58:

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

input:

3000 3000
10 903 639468436 3211533151
227 1344 926811751
1919 1949 837083439
228 638 141284653
2137 2481 840777783
667 885 983425115
527 2975 541524579
1937 2752 777540325
48 1745 951895032
1146 2285 865318421
247 2247 524068937
347 2846 407037626
1074 2949 229857419
611 1217 169780190
1810 2031 604...

output:

253

result:

ok single line: '253'

Test #59:

score: 29
Accepted
time: 3ms
memory: 14340kb

input:

3000 3000
1141 2362 235601608 524309034840309
1741 2548 75242545
868 1358 157029860
708 1793 182150282
571 2794 648800173
100 1815 496177778
2174 2439 738541998
1962 2024 882029519
1031 1853 773454049
1215 1644 424709187
1946 2763 479842947
683 2326 461077188
2487 2608 781511670
1497 2455 390810057
...

output:

2376

result:

ok single line: '2376'

Test #60:

score: 29
Accepted
time: 2ms
memory: 15664kb

input:

3000 2999
2355 2768 445337968 951809992
1 1312 868240697
2 1312 678422653
3 1312 470112241
4 1312 287865697
5 1312 795471532
6 1312 515973225
7 1312 676155032
8 1312 129913532
9 1312 512705401
10 1312 156951202
11 1312 260465388
12 1312 852576523
13 1312 472285618
14 1312 275211045
15 1312 382241208...

output:

976

result:

ok single line: '976'

Test #61:

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

input:

3000 2999
630 1827 78958062 535102127
1 2787 632369519
2 2787 599104976
3 2787 547934290
4 2787 213249600
5 2787 367076117
6 2787 594980655
7 2787 428235794
8 2787 94512657
9 2787 574535841
10 2787 4815945
11 2787 404101641
12 2787 828498741
13 2787 149032176
14 2787 43195102
15 2787 49501417
16 278...

output:

427

result:

ok single line: '427'

Test #62:

score: 29
Accepted
time: 3ms
memory: 14172kb

input:

1502 2998
1 1502 60615603 60616185
2 3 2
3 1501 999999994
2 4 3
4 1501 999999992
2 5 4
5 1501 999999990
2 6 5
6 1501 999999988
2 7 6
7 1501 999999986
2 8 7
8 1501 999999984
2 9 8
9 1501 999999982
2 10 9
10 1501 999999980
2 11 10
11 1501 999999978
2 12 11
12 1501 999999976
2 13 12
13 1501 999999974
2...

output:

1163

result:

ok single line: '1163'

Test #63:

score: 29
Accepted
time: 3ms
memory: 14476kb

input:

1502 2998
1 1502 462744981 462745160
2 3 2
3 1501 999999994
2 4 3
4 1501 999999992
2 5 4
5 1501 999999990
2 6 5
6 1501 999999988
2 7 6
7 1501 999999986
2 8 7
8 1501 999999984
2 9 8
9 1501 999999982
2 10 9
10 1501 999999980
2 11 10
11 1501 999999978
2 12 11
12 1501 999999976
2 13 12
13 1501 999999974...

output:

357

result:

ok single line: '357'

Test #64:

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

input:

2001 3000
225 1222 1 6
1 2 3
2 3 4
3 4 6
4 5 10
5 6 18
6 7 34
7 8 66
8 9 130
9 10 258
10 11 514
11 12 1026
12 13 2050
13 14 4098
14 15 8194
15 16 16386
16 17 32770
17 18 65538
18 19 131074
19 20 262146
20 21 524290
21 22 1048578
22 23 2097154
23 24 4194306
24 25 8388610
25 26 16777218
26 27 33554434...

output:

61

result:

ok single line: '61'

Test #65:

score: 29
Accepted
time: 4ms
memory: 15168kb

input:

2001 3000
999 1986 7 18
1 2 3
2 3 4
3 4 6
4 5 10
5 6 18
6 7 34
7 8 66
8 9 130
9 10 258
10 11 514
11 12 1026
12 13 2050
13 14 4098
14 15 8194
15 16 16386
16 17 32770
17 18 65538
18 19 131074
19 20 262146
20 21 524290
21 22 1048578
22 23 2097154
23 24 4194306
24 25 8388610
25 26 16777218
26 27 3355443...

output:

216

result:

ok single line: '216'

Subtask #4:

score: 47
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #66:

score: 47
Accepted
time: 69ms
memory: 22520kb

input:

200000 200000
140377 172310 1000000000 1000000000000000
139359 192279 1000000000
87491 120039 1000000000
155799 184344 1000000000
85411 109154 1000000000
31905 47597 1000000000
20672 39093 1000000000
177632 189999 1000000000
80786 102779 1000000000
113020 132204 1000000000
48033 48622 1000000000
184...

output:

19999900000

result:

ok single line: '19999900000'

Test #67:

score: 47
Accepted
time: 57ms
memory: 24704kb

input:

200000 200000
182280 185822 1000000000 1000000000000000
104863 129723 1000000000
149590 180426 1000000000
144033 167801 1000000000
75549 96900 1000000000
25304 44539 1000000000
34702 49080 1000000000
117218 125469 1000000000
80717 126396 1000000000
41417 57212 1000000000
16619 40449 1000000000
98748...

output:

19999900000

result:

ok single line: '19999900000'

Test #68:

score: 47
Accepted
time: 94ms
memory: 26820kb

input:

200000 200000
12665 142075 1000000000 1000000000000000
141322 192637 1000000000
70431 126919 1000000000
806 16259 1000000000
79488 95678 1000000000
80134 113457 1000000000
177447 180370 1000000000
84488 90091 1000000000
10736 50457 1000000000
148167 163102 1000000000
104695 127727 1000000000
17255 6...

output:

53272

result:

ok single line: '53272'

Test #69:

score: 47
Accepted
time: 26ms
memory: 22904kb

input:

632 199396
497 606 741613 7730197
118 563 781033571
372 565 278716411
487 498 660126241
91 491 558756944
309 535 896550712
91 620 46181351
11 233 973386889
493 551 299305553
224 507 359744941
47 218 144003592
153 520 869612047
380 563 669317190
526 574 306410296
316 584 888962894
300 330 425968393
1...

output:

199396

result:

ok single line: '199396'

Test #70:

score: 47
Accepted
time: 29ms
memory: 23908kb

input:

632 199396
455 533 438583 9998656
2 172 467717703
293 452 200813130
6 364 866414747
196 541 91687443
15 22 858731011
247 320 12424804
231 365 69141569
335 361 204322434
114 432 165378177
82 613 423246011
452 548 928470035
247 282 6758792
270 463 685436491
246 295 376813760
406 562 116606983
210 346 ...

output:

6698

result:

ok single line: '6698'

Test #71:

score: 47
Accepted
time: 55ms
memory: 21380kb

input:

200000 100000
36033 186265 125948044 432582804225
115274 119845 984740829
47322 108536 568030888
112714 159934 931642279
32778 63309 429979437
5490 135867 276580357
14658 153653 237847969
153727 198812 454750704
8841 96638 651168007
39877 195144 667722943
68898 93645 457435146
25174 118936 229968207...

output:

267

result:

ok single line: '267'

Test #72:

score: 47
Accepted
time: 64ms
memory: 21388kb

input:

200000 100000
74188 179656 880255121 167620056859
44005 136787 683797881
50544 195929 88054211
23581 171892 785162267
3209 144169 778699892
162731 181181 776001262
79157 148349 226648709
107492 165191 412776373
23927 163489 623441217
18289 145140 57525565
105678 150825 38881993
3438 165568 825425404...

output:

1323

result:

ok single line: '1323'

Test #73:

score: 47
Accepted
time: 198ms
memory: 84812kb

input:

200000 200000
17401 78087 406531130 5970579883
48007 144983 910671808
48451 175318 252396889
140768 145986 31550062
84079 193440 303911430
126712 176069 285693010
3663 25149 588337653
18584 49244 748422859
79395 100103 61327878
72468 167688 34798301
60264 199739 569764999
60735 100946 440741095
3853...

output:

989006

result:

ok single line: '989006'

Test #74:

score: 47
Accepted
time: 103ms
memory: 22976kb

input:

200000 200000
141865 156042 805963199 5896293989
12170 158091 702408824
79747 126630 174793764
154634 171257 708318040
30416 54978 383114238
10678 146016 793375237
66856 97999 49125311
137004 167404 349041750
50527 128440 560662572
96237 113382 507590752
43177 88037 232881416
7845 123663 249891489
1...

output:

19999900000

result:

ok single line: '19999900000'

Test #75:

score: 47
Accepted
time: 304ms
memory: 140260kb

input:

199920 200000
48640 163229 1 4016382532515
3747 164390 946945501
132262 135339 386057353
72443 106034 491658194
41731 60216 793977245
2974 21919 34494340
107450 181150 137359604
18049 120073 192848564
99887 157330 718445601
19842 146708 56506359
124792 179417 999011513
82320 176120 992167197
7161 26...

output:

3675399301

result:

ok single line: '3675399301'

Test #76:

score: 47
Accepted
time: 281ms
memory: 166788kb

input:

200000 200000
75253 174366 1 55163353281637
169946 174259 64987025
103349 119083 59055199
149193 170980 944024505
69035 185515 681354289
4490 171390 261037544
4890 178886 642893884
106762 113316 948752962
143926 165587 222998000
28024 127665 415584335
173519 180121 439546113
36884 155599 550312371
8...

output:

12299869306

result:

ok single line: '12299869306'

Test #77:

score: 47
Accepted
time: 125ms
memory: 165920kb

input:

200000 199999
20040 192101 745801598 43015463916707
1 2 289876625
2 3 593164432
3 4 493046146
4 5 446541799
5 6 847597426
6 7 845380484
7 8 337978988
8 9 548959676
9 10 516746529
10 11 4752633
11 12 113779090
12 13 282266133
13 14 753174008
14 15 242844419
15 16 257690768
16 17 437737751
17 18 85743...

output:

6023927413

result:

ok single line: '6023927413'

Test #78:

score: 47
Accepted
time: 110ms
memory: 165248kb

input:

200000 199999
5615 32236 385669222 6669305784382
1 2 35378456
2 3 266047357
3 4 958219452
4 5 421932383
5 6 411035604
6 7 406572496
7 8 417830538
8 9 731478193
9 10 157080827
10 11 711614837
11 12 236841327
12 13 422096352
13 14 640633339
14 15 716277841
15 16 79035804
16 17 140104126
17 18 71239943...

output:

295959117

result:

ok single line: '295959117'

Test #79:

score: 47
Accepted
time: 25ms
memory: 24168kb

input:

632 199396
497 606 741613 4606711
118 563 781033571
372 565 278716411
487 498 660126241
91 491 558756944
309 535 896550712
91 620 46181351
11 233 973386889
493 551 299305553
224 507 359744941
47 218 144003592
153 520 869612047
380 563 669317190
526 574 306410296
316 584 888962894
300 330 425968393
1...

output:

45

result:

ok single line: '45'

Test #80:

score: 47
Accepted
time: 41ms
memory: 22300kb

input:

632 199396
455 533 438583 5612505
2 172 467717703
293 452 200813130
6 364 866414747
196 541 91687443
15 22 858731011
247 320 12424804
231 365 69141569
335 361 204322434
114 432 165378177
82 613 423246011
452 548 928470035
247 282 6758792
270 463 685436491
246 295 376813760
406 562 116606983
210 346 ...

output:

327

result:

ok single line: '327'

Test #81:

score: 47
Accepted
time: 60ms
memory: 21492kb

input:

200000 100000
36033 186265 125948044 241421658784924
115274 119845 984740829
47322 108536 568030888
112714 159934 931642279
32778 63309 429979437
5490 135867 276580357
14658 153653 237847969
153727 198812 454750704
8841 96638 651168007
39877 195144 667722943
68898 93645 457435146
25174 118936 229968...

output:

267

result:

ok single line: '267'

Test #82:

score: 47
Accepted
time: 57ms
memory: 21380kb

input:

200000 100000
74188 179656 880255121 776856620056859
44005 136787 683797881
50544 195929 88054211
23581 171892 785162267
3209 144169 778699892
162731 181181 776001262
79157 148349 226648709
107492 165191 412776373
23927 163489 623441217
18289 145140 57525565
105678 150825 38881993
3438 165568 825425...

output:

1323

result:

ok single line: '1323'

Test #83:

score: 47
Accepted
time: 207ms
memory: 84164kb

input:

200000 200000
17401 78087 406531130 3459801425
48007 144983 910671808
48451 175318 252396889
140768 145986 31550062
84079 193440 303911430
126712 176069 285693010
3663 25149 588337653
18584 49244 748422859
79395 100103 61327878
72468 167688 34798301
60264 199739 569764999
60735 100946 440741095
3853...

output:

7856

result:

ok single line: '7856'

Test #84:

score: 47
Accepted
time: 203ms
memory: 84776kb

input:

200000 200000
141865 156042 805963199 3754110193
12170 158091 702408824
79747 126630 174793764
154634 171257 708318040
30416 54978 383114238
10678 146016 793375237
66856 97999 49125311
137004 167404 349041750
50527 128440 560662572
96237 113382 507590752
43177 88037 232881416
7845 123663 249891489
1...

output:

4822

result:

ok single line: '4822'

Test #85:

score: 47
Accepted
time: 207ms
memory: 91112kb

input:

200000 199999
76625 123007 119910860 298702972
1 76625 593164432
2 76625 493046146
3 76625 446541799
4 76625 847597426
5 76625 845380484
6 76625 337978988
7 76625 548959676
8 76625 516746529
9 76625 4752633
10 76625 113779090
11 76625 282266133
12 76625 753174008
13 76625 242844419
14 76625 25769076...

output:

35844

result:

ok single line: '35844'

Test #86:

score: 47
Accepted
time: 184ms
memory: 88736kb

input:

200000 199999
4427 178456 259830768 587921545
1 178456 266047357
2 178456 958219452
3 178456 421932383
4 178456 411035604
5 178456 406572496
6 178456 417830538
7 178456 731478193
8 178456 157080827
9 178456 711614837
10 178456 236841327
11 178456 422096352
12 178456 640633339
13 178456 716277841
14 ...

output:

65678

result:

ok single line: '65678'

Test #87:

score: 47
Accepted
time: 74ms
memory: 28708kb

input:

100002 199998
1 100002 252386893 252429925
2 3 2
3 100001 999999994
2 4 3
4 100001 999999992
2 5 4
5 100001 999999990
2 6 5
6 100001 999999988
2 7 6
7 100001 999999986
2 8 7
8 100001 999999984
2 9 8
9 100001 999999982
2 10 9
10 100001 999999980
2 11 10
11 100001 999999978
2 12 11
12 100001 999999976...

output:

86063

result:

ok single line: '86063'

Test #88:

score: 47
Accepted
time: 77ms
memory: 28692kb

input:

100002 199998
1 100002 252331960 252359564
2 3 2
3 100001 999999994
2 4 3
4 100001 999999992
2 5 4
5 100001 999999990
2 6 5
6 100001 999999988
2 7 6
7 100001 999999986
2 8 7
8 100001 999999984
2 9 8
9 100001 999999982
2 10 9
10 100001 999999980
2 11 10
11 100001 999999978
2 12 11
12 100001 999999976...

output:

55207

result:

ok single line: '55207'

Test #89:

score: 47
Accepted
time: 88ms
memory: 28556kb

input:

133333 199998
2269 76076 4558 12452
1 2 3
2 3 4
3 4 6
4 5 10
5 6 18
6 7 34
7 8 66
8 9 130
9 10 258
10 11 514
11 12 1026
12 13 2050
13 14 4098
14 15 8194
15 16 16386
16 17 32770
17 18 65538
18 19 131074
19 20 262146
20 21 524290
21 22 1048578
22 23 2097154
23 24 4194306
24 25 8388610
25 26 16777218
2...

output:

113370097

result:

ok single line: '113370097'

Test #90:

score: 47
Accepted
time: 84ms
memory: 28820kb

input:

133333 199998
38693 93376 9568 12241
1 2 3
2 3 4
3 4 6
4 5 10
5 6 18
6 7 34
7 8 66
8 9 130
9 10 258
10 11 514
11 12 1026
12 13 2050
13 14 4098
14 15 8194
15 16 16386
16 17 32770
17 18 65538
18 19 131074
19 20 262146
20 21 524290
21 22 1048578
22 23 2097154
23 24 4194306
24 25 8388610
25 26 16777218
...

output:

14295205

result:

ok single line: '14295205'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-05 00:56:36 | OpenSource Project