QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#120561#1152. DreamingQwerty1232#100 ✓39ms17440kbC++172.2kb2023-07-06 21:40:162024-05-26 02:55:28

Judging History

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

  • [2024-05-26 02:55:28]
  • 评测
  • 测评结果:100
  • 用时:39ms
  • 内存:17440kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-06 21:40:16]
  • 提交

answer

#include "dreaming.h"

#include <bits/stdc++.h>

int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    if (n == 1) {
        return 0;
    }
    // if (n == 2) {
    //     if (m == 0) {
    //         return L;
    //     }
    //     return T[0];
    // }
    std::vector<std::vector<std::pair<int, int>>> gr(n);
    for (int i = 0; i < m; i++) {
        gr[A[i]].push_back({B[i], T[i]});
        gr[B[i]].push_back({A[i], T[i]});
    }

    int ans = 0;
    std::vector<bool> used(n);
    std::vector<int> dist(n), prv(n);
    std::vector<int> cum;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            std::vector<int> vec;
            auto dfs = [&](auto dfs, int v, int f, int d) -> void {
                used[v] = true;
                dist[v] = d;
                vec.push_back(v);
                for (auto [t, w] : gr[v]) {
                    if (t != f) {
                        dfs(dfs, t, v, d + w);
                    }
                }
            };
            dfs(dfs, i, -1, 0);
            int it = *std::max_element(vec.begin(), vec.end(), [&](int a, int b) { return dist[a] < dist[b]; });
            auto dfs2 = [&](auto dfs2, int v, int f, int d) -> void {
                dist[v] = d;
                prv[v] = f;
                for (auto [t, w] : gr[v]) {
                    if (t != f) {
                        dfs2(dfs2, t, v, d + w);
                    }
                }
            };
            dfs2(dfs2, it, -1, 0);
            int fr = *std::max_element(vec.begin(), vec.end(), [&](int a, int b) { return dist[a] < dist[b]; });
            int u = fr;
            int res = dist[fr];
            while (u != it) {
                res = std::min(res, std::max(dist[u], dist[fr] - dist[u]));
                u = prv[u];
            }
            ans = std::max(ans, dist[fr]);
            cum.push_back(res);
        }
    }
    std::sort(cum.begin(), cum.end());
    if (cum.size() > 1) {
        ans = std::max(ans, cum.rbegin()[1] + cum.back() + L);
    }
    if (cum.size() > 2) {
        ans = std::max(ans, cum.rbegin()[1] + cum.rbegin()[2] + 2 * L);
    }
    return ans;
}

详细

Subtask #1:

score: 14
Accepted

Test #1:

score: 14
Accepted
time: 31ms
memory: 14316kb

input:

91188 91186 10000
39179 82675 10000
79545 19393 3
19393 31673 7
31673 40086 4
40086 14128 2
14128 38440 10
38440 40431 4
40431 67403 8
67403 77400 9
77400 21224 10
21224 65903 9
65903 9211 10
9211 37061 2
37061 70742 10
70742 72699 10
72699 11504 3
11504 63531 7
63531 10974 7
10974 17289 9
17289 234...

output:

511231

result:

ok single line: '511231'

Test #2:

score: 14
Accepted
time: 27ms
memory: 14556kb

input:

90985 90983 10000
17893 45320 10000
9795 38629 8
38629 30491 2
30491 58120 2
58120 53925 7
53925 40895 5
40895 71265 1
71265 57244 7
57244 5784 2
5784 74929 4
74929 50701 6
50701 9254 7
9254 677 6
677 26842 6
26842 63528 10
63528 69055 2
69055 65844 1
65844 33629 10
33629 45089 8
45089 47663 7
47663...

output:

509117

result:

ok single line: '509117'

Test #3:

score: 14
Accepted
time: 20ms
memory: 11184kb

input:

59727 59725 10000
12924 21291 3050
8628 24496 2385
24496 34225 8813
34225 46357 2318
46357 12586 1963
12586 53685 8626
53685 46172 7435
46172 38200 6712
38200 14955 105
14955 53575 8582
53575 54033 1405
54033 27453 7452
27453 25895 7090
25895 52446 5230
52446 6860 429
6860 1608 5869
1608 48065 38
48...

output:

297476049

result:

ok single line: '297476049'

Test #4:

score: 14
Accepted
time: 4ms
memory: 5256kb

input:

13379 13377 10000
8612 3040 1270
1684 931 2038
931 3858 2689
3858 11652 3774
11652 10719 9155
10719 6711 3990
6711 10837 7538
10837 11886 2637
11886 11045 5956
11045 11038 5181
11038 12615 7106
12615 7837 1076
7837 1429 4307
1429 2708 2822
2708 13072 8354
13072 10193 1289
10193 987 8196
987 11013 12...

output:

66948810

result:

ok single line: '66948810'

Test #5:

score: 14
Accepted
time: 4ms
memory: 4596kb

input:

10000 9998 9384
961 4543 1
4900 8661 1
9505 5506 1
8765 2772 1
234 9833 1
8744 5598 1
1538 3835 1
3791 376 9658
7239 4176 9194
8873 7353 1
698 3842 1
3541 9279 9570
3838 2054 1
4997 6161 1
2462 3707 1
3186 8819 9561
1564 6076 9793
4537 4357 9186
3167 1556 9630
3926 9818 1
3095 6929 9942
6327 5855 1
...

output:

47065288

result:

ok single line: '47065288'

Test #6:

score: 14
Accepted
time: 5ms
memory: 5788kb

input:

20000 19998 1
2523 15971 9495
11768 2000 9182
6405 18468 9766
15539 12729 9207
641 19545 9381
5924 7984 9226
611 4489 9696
11138 19245 9801
4677 656 9805
6005 5795 9655
8382 8399 9411
3397 5483 9607
10587 6792 9725
8356 10591 9577
18468 10523 9646
14460 1550 9983
8966 10852 9074
982 4707 9494
17816 ...

output:

188827927

result:

ok single line: '188827927'

Test #7:

score: 14
Accepted
time: 1ms
memory: 3928kb

input:

300 298 9837
137 145 2
207 27 2
9 17 1
203 130 1
99 243 2
120 192 1
80 5 2
152 47 2
26 169 2
65 234 1
39 149 1
246 207 1
228 150 1
241 171 1
271 209 2
37 55 2
24 60 2
293 230 1
244 133 1
192 95 1
134 275 1
46 71 1
2 93 1
253 4 2
256 245 2
64 166 2
224 259 2
167 265 2
49 226 1
161 204 2
30 197 2
101 ...

output:

10067

result:

ok single line: '10067'

Test #8:

score: 14
Accepted
time: 12ms
memory: 7704kb

input:

40000 39998 3473
25173 14268 1
23259 28143 1
5031 25559 1
10309 14102 1
25915 11048 1
21078 2106 1
22225 13591 1
32736 36144 1
16976 21159 1
9275 26622 1
12925 12501 1
20410 29233 1
30685 15471 1
536 29041 1
17365 32848 1
13714 17218 1
36637 21881 1
33023 19650 1
9647 24621 1
1924 8495 1
33902 35009...

output:

1525624

result:

ok single line: '1525624'

Test #9:

score: 14
Accepted
time: 17ms
memory: 9664kb

input:

50000 49998 2
3451 1014 1
21904 13342 1
40227 287 9767
21008 18596 2
21096 47312 1
14775 47545 1
27254 37482 2
11149 49857 9360
23107 14653 2
27687 19956 1
15953 18441 1
33041 45149 9642
3040 18993 1
25008 4882 2
49070 41491 9733
43251 40955 1
1877 18741 1
3492 29550 9207
15465 47785 9859
26747 7359...

output:

93799588

result:

ok single line: '93799588'

Test #10:

score: 14
Accepted
time: 1ms
memory: 3988kb

input:

600 598 9510
115 362 2
462 538 1
456 350 1
339 457 2
351 26 2
60 361 1
268 329 1
118 211 1
572 136 2
124 179 1
250 198 1
384 456 1
129 93 2
221 427 1
69 596 2
101 183 1
135 96 1
330 33 2
486 308 1
394 222 1
256 214 1
463 399 2
191 251 1
139 287 2
478 464 1
332 65 2
299 158 2
470 575 1
16 581 1
509 4...

output:

9971

result:

ok single line: '9971'

Test #11:

score: 14
Accepted
time: 25ms
memory: 11040kb

input:

70000 69998 2461
41073 45496 9654
51790 8309 2342
46664 18809 9984
5102 60744 1462
34753 54183 9255
16084 543 9626
52687 58277 2488
49468 35642 9539
1839 25292 9661
21159 53291 9458
59186 52461 9895
56198 27804 9740
32676 56525 9056
27099 20218 9106
24289 48456 9416
14693 52984 7308
34844 4305 9916
...

output:

451936219

result:

ok single line: '451936219'

Test #12:

score: 14
Accepted
time: 33ms
memory: 12512kb

input:

80000 79998 3
12230 7310 2
44021 21654 2
13540 21312 1
14682 21596 1
3330 70281 9476
6505 69355 2
22068 73465 1
7716 6854 1
16967 55118 2
71712 6005 1
78087 71551 1
50697 75227 9222
41137 69251 2
70406 78085 2
49491 24360 1
25924 22656 2
73092 25860 2
59671 19933 1
28686 2675 1
60739 11636 9033
1124...

output:

104016795

result:

ok single line: '104016795'

Test #13:

score: 14
Accepted
time: 1ms
memory: 4228kb

input:

900 898 9762
706 259 1
85 823 1
536 168 2
773 359 2
210 379 2
857 271 1
811 286 2
681 342 1
416 883 2
685 830 1
70 771 2
319 454 2
193 678 2
528 62 2
330 137 1
732 612 2
657 733 1
166 872 1
255 560 1
496 13 1
322 520 2
30 802 2
745 729 2
566 536 2
790 302 1
109 88 1
506 820 2
176 9 2
855 607 2
677 2...

output:

10433

result:

ok single line: '10433'

Subtask #2:

score: 10
Accepted

Test #14:

score: 10
Accepted
time: 1ms
memory: 3840kb

input:

100 98 1
43 79 282
31 57 4
1 42 1
33 52 2
25 93 1
30 94 1
15 81 2
30 67 2
23 10 4
31 32 1
56 1 1
97 53 5
71 87 2
17 76 4
65 45 3
86 37 3
86 12 2
85 96 1
71 66 2
73 98 5
78 97 3
43 74 1
21 68 5
23 6 5
35 9 1
38 58 2
72 92 1
12 4 5
70 15 2
7 64 5
28 70 2
48 28 5
22 3 2
41 66 5
18 27 4
67 91 4
11 91 3
...

output:

340

result:

ok single line: '340'

Test #15:

score: 10
Accepted
time: 0ms
memory: 3900kb

input:

100 98 1
53 23 227
18 80 4
49 1 5
91 20 1
41 2 5
16 87 1
59 7 2
83 91 1
40 92 1
52 21 5
77 89 3
86 13 3
11 9 5
19 93 5
76 3 1
73 50 4
8 57 1
84 35 5
29 40 5
61 56 3
6 31 4
99 30 3
61 49 5
58 75 4
33 54 2
66 36 4
48 98 4
77 78 5
82 60 1
94 65 5
37 68 5
17 88 3
34 66 5
44 8 2
51 84 2
71 79 4
27 44 5
1...

output:

266

result:

ok single line: '266'

Test #16:

score: 10
Accepted
time: 1ms
memory: 3836kb

input:

100 98 539
49 97 7
16 43 10
39 80 4
51 25 9
81 67 3
79 75 7
24 20 1
21 29 5
3 6 5
8 47 7
55 63 7
19 63 6
66 54 7
40 89 8
91 41 10
64 31 2
90 78 8
60 69 2
62 61 5
5 84 4
72 55 4
0 69 6
73 68 3
21 67 2
6 32 5
7 73 1
18 65 1
99 33 7
61 15 8
74 1 7
67 38 8
82 54 1
13 72 5
88 26 10
3 49 6
87 48 10
43 83 ...

output:

649

result:

ok single line: '649'

Test #17:

score: 10
Accepted
time: 0ms
memory: 3836kb

input:

100 98 497
94 87 7
2 88 9
23 98 3
67 92 9
3 90 6
36 40 5
80 50 10
42 43 10
51 53 5
24 71 9
92 73 10
75 87 6
15 57 2
98 12 1
84 54 1
11 20 4
44 49 6
97 12 6
11 74 10
18 3 6
17 4 10
48 60 6
85 27 8
0 5 3
59 99 3
68 34 6
20 94 6
89 65 5
39 70 3
59 76 7
62 36 6
57 92 5
64 96 10
44 98 10
35 58 4
55 9 2
5...

output:

638

result:

ok single line: '638'

Test #18:

score: 10
Accepted
time: 1ms
memory: 3796kb

input:

100 98 997
4 51 251
18 7 522
47 98 900
48 32 87
61 9 236
76 5 109
98 62 450
16 37 315
93 57 613
84 81 692
9 24 224
83 19 144
78 49 372
37 94 778
90 24 377
64 56 369
92 1 654
99 82 737
50 55 378
67 22 303
7 31 730
7 6 302
91 58 951
41 13 216
56 51 92
14 39 300
0 79 965
60 68 446
98 30 704
27 53 519
7...

output:

11447

result:

ok single line: '11447'

Test #19:

score: 10
Accepted
time: 0ms
memory: 3836kb

input:

100 98 1000
16 8 364
42 53 909
21 25 494
53 77 1000
79 59 372
54 88 86
95 21 2
88 50 929
82 92 369
57 22 143
60 61 527
63 38 974
49 87 375
40 91 520
53 68 578
93 98 454
45 34 777
89 69 417
30 21 611
62 55 606
38 23 14
99 12 759
74 29 362
69 84 658
20 23 724
13 26 59
53 66 824
24 26 873
25 31 827
33 ...

output:

8525

result:

ok single line: '8525'

Test #20:

score: 10
Accepted
time: 0ms
memory: 3848kb

input:

100 98 10000
0 84 10000
99 87 4
98 96 3
97 0 3
22 74 6
98 0 10
94 80 7
95 30 9
93 5 7
91 55 5
42 79 6
99 40 8
21 83 5
90 84 7
86 17 2
20 63 7
56 34 2
24 9 9
85 78 10000
81 33 1
94 4 7
4 82 5
4 72 6
4 86 9
80 52 4
52 15 6
82 68 1
52 53 3
17 12 7
17 77 4
12 60 2
94 56 2
80 50 7
53 70 4
60 71 9
94 76 4...

output:

30010

result:

ok single line: '30010'

Test #21:

score: 10
Accepted
time: 1ms
memory: 4132kb

input:

100 98 10000
0 16 10000
99 31 4
98 88 8
97 21 3
96 91 1
13 25 6
95 14 6
93 49 2
8 16 9
92 10 6
90 28 7
89 42 7
98 57 10
88 52 7
88 7 8
88 54 1
82 46 4
70 56 3
57 34 2
54 33 7
52 47 10
88 18 9
7 84 8
57 37 3
7 78 9
52 32 4
98 51 8
98 71 7
18 56 6
52 63 2
52 27 10
27 40 1
6 53 8
47 20 6
70 75 4
97 12 ...

output:

30009

result:

ok single line: '30009'

Test #22:

score: 10
Accepted
time: 0ms
memory: 3840kb

input:

100 98 10000
0 81 446
99 93 1383
98 23 2933
97 86 3598
96 18 3542
95 65 1199
5 67 9527
94 70 4110
92 7 3559
91 19 5479
90 33 7492
89 11 4151
88 57 7372
87 63 1366
97 49 4078
40 7 9228
49 2 3652
2 66 831
49 48 7566
49 56 6213
18 42 8476
48 64 8445
97 74 4973
97 32 4361
48 10 1655
66 35 8754
64 77 245...

output:

91413

result:

ok single line: '91413'

Test #23:

score: 10
Accepted
time: 0ms
memory: 3840kb

input:

100 98 10000
84 90 8665
0 15 6517
98 20 5221
97 6 8059
96 1 4186
95 85 8354
94 79 5536
93 40 4967
92 51 7756
91 49 7876
84 38 7250
38 18 4434
18 81 546
54 66 4114
78 52 1655
38 83 9539
90 87 7548
87 13 6739
38 48 3531
87 71 4500
84 5 7764
5 9 5755
13 97 4247
83 22 3590
9 39 5906
5 63 234
13 89 1710
...

output:

90337

result:

ok single line: '90337'

Test #24:

score: 10
Accepted
time: 1ms
memory: 3768kb

input:

100 98 10000
48 12 10000
79 72 10000
71 63 6
98 61 6
58 42 2
99 39 5
11 82 9
46 99 9
3 8 9
77 0 10
92 7 9
29 83 7
56 31 8
8 87 2
57 68 6
73 61 1
28 50 2
3 55 5
94 13 8
30 4 2
11 85 2
50 80 8
41 19 2
72 45 6
47 34 1
24 69 8
26 19 2
76 15 9
90 75 4
97 56 8
64 44 10
22 28 3
92 64 7
32 83 7
2 72 10
20 5...

output:

30024

result:

ok single line: '30024'

Test #25:

score: 10
Accepted
time: 0ms
memory: 3832kb

input:

100 98 10000
86 53 10000
23 24 8
19 62 10000
77 1 10
93 99 3
41 64 2
88 16 10
27 69 9
58 60 4
84 25 5
32 42 4
32 68 9
85 45 9
72 51 6
48 90 4
22 21 1
4 70 1
22 52 10
5 98 4
16 63 2
41 30 5
7 59 5
12 29 5
8 71 8
85 67 5
44 65 8
51 1 8
64 61 3
98 66 10
7 44 7
3 78 5
32 97 6
57 73 6
25 46 2
34 56 10
88...

output:

30024

result:

ok single line: '30024'

Test #26:

score: 10
Accepted
time: 1ms
memory: 3872kb

input:

100 98 10000
90 76 5824
98 43 9151
18 87 9381
96 57 5765
6 64 4269
56 83 4545
54 1 2445
66 5 7765
52 30 5255
19 51 2644
64 47 9165
95 37 4800
48 71 5042
41 2 4172
20 15 5244
35 63 3623
53 36 7585
44 65 5838
40 42 4870
88 90 2377
35 45 9075
40 48 347
20 43 1685
95 55 3749
59 31 9918
27 7 4849
21 14 1...

output:

104332

result:

ok single line: '104332'

Test #27:

score: 10
Accepted
time: 0ms
memory: 3896kb

input:

100 98 10000
65 77 2410
20 84 6610
84 89 3880
27 50 7172
10 99 9430
83 31 8077
97 22 2538
90 78 1218
54 8 7125
55 44 7485
91 9 8417
3 75 1619
57 76 6357
13 70 3964
76 40 1017
6 70 1483
36 21 9689
66 94 6664
74 69 8819
62 12 2202
57 36 1823
37 53 9471
79 82 9398
58 11 915
19 47 9676
20 98 51
2 5 342
...

output:

174172

result:

ok single line: '174172'

Test #28:

score: 10
Accepted
time: 1ms
memory: 3888kb

input:

2 0 5018


output:

5018

result:

ok single line: '5018'

Test #29:

score: 10
Accepted
time: 1ms
memory: 3900kb

input:

97 95 2
95 78 2
4 35 9850
86 78 2
94 35 9238
45 78 2
23 35 9117
65 28 9276
50 35 9869
54 78 2
3 35 9879
79 78 1
93 78 2
59 78 2
42 78 2
77 78 1
87 35 9604
1 61 9506
80 35 9630
83 35 9933
75 35 9167
24 74 2
10 35 9567
58 35 9584
11 87 9492
41 35 9652
29 35 9752
82 35 9976
73 78 2
67 83 9240
70 78 1
4...

output:

39372

result:

ok single line: '39372'

Test #30:

score: 10
Accepted
time: 1ms
memory: 3808kb

input:

97 95 4
71 53 2
22 53 2
41 2 1
14 2 1
52 53 1
74 66 1
5 2 2
18 41 1
31 2 2
72 2 1
82 13 2
53 2 1
54 2 2
1 2 1
56 2 2
39 89 1
76 2 1
28 2 1
60 2 1
58 84 1
50 53 1
44 2 1
86 2 1
78 53 2
51 13 1
80 2 1
89 2 1
24 2 1
6 2 1
84 2 2
69 95 1
61 13 2
37 2 2
81 53 2
43 2 1
92 53 2
25 89 2
11 53 2
77 2 2
0 2 1...

output:

8

result:

ok single line: '8'

Test #31:

score: 10
Accepted
time: 0ms
memory: 4136kb

input:

92 90 1
18 49 2
71 24 1
65 89 2
44 15 1
74 23 1
61 91 1
46 59 2
35 4 1
86 9 2
68 62 1
70 19 2
14 56 2
57 79 1
41 62 2
39 34 2
23 59 1
53 88 2
36 17 2
13 42 1
64 34 1
0 52 1
67 20 2
43 74 1
56 83 2
88 25 1
34 89 2
80 13 2
19 45 1
17 25 1
84 30 1
82 62 1
48 69 2
9 54 2
63 2 2
49 16 2
5 33 2
75 37 2
27...

output:

72

result:

ok single line: '72'

Test #32:

score: 10
Accepted
time: 1ms
memory: 3912kb

input:

99 97 1
37 2 9904
45 87 9948
33 66 9821
41 2 9842
25 84 9474
57 91 9941
74 52 2
28 44 9090
32 78 2
77 27 9782
0 60 9753
30 22 9427
97 3 9298
69 11 9870
43 62 9073
85 2 9209
11 20 9997
36 78 2
59 2 9777
86 40 9771
58 51 9364
8 80 9511
40 69 9338
21 69 9807
7 60 9973
9 12 9527
93 96 9946
4 93 9688
67 ...

output:

125532

result:

ok single line: '125532'

Test #33:

score: 10
Accepted
time: 1ms
memory: 3840kb

input:

93 91 9
83 11 2
87 19 2
86 45 1
49 64 9661
28 42 2
61 57 1
56 34 9891
79 43 1
77 33 1
33 46 1
80 88 2
59 62 9243
54 11 2
74 23 9230
81 92 9948
75 30 9967
35 13 9262
76 1 1
15 12 1
22 24 1
72 75 9313
58 79 2
6 62 9955
57 25 2
46 63 1
64 62 9772
20 0 9523
27 41 1
52 7 2
12 37 1
84 42 1
48 59 9090
23 4...

output:

102505

result:

ok single line: '102505'

Test #34:

score: 10
Accepted
time: 1ms
memory: 3828kb

input:

99 97 6
88 97 2
46 97 2
17 37 1
24 97 2
82 93 1
75 37 2
8 61 1
33 37 2
90 97 1
52 97 1
23 37 2
1 93 2
94 37 2
54 93 2
77 93 2
10 96 2
81 97 1
19 37 2
58 97 1
61 37 1
41 37 2
56 21 1
2 37 2
27 24 2
32 97 2
59 93 2
55 93 1
57 97 1
80 97 2
69 37 2
44 37 2
4 37 2
96 61 2
18 97 2
48 37 1
60 21 2
91 37 2
...

output:

15

result:

ok single line: '15'

Test #35:

score: 10
Accepted
time: 1ms
memory: 3840kb

input:

99 97 10
51 6 9023
92 47 9311
58 79 1
45 53 9764
20 74 9700
80 87 9868
10 20 9139
96 51 9239
35 28 1
82 28 1
90 43 2
11 83 1
31 2 9375
24 10 9392
50 45 9973
27 57 9678
53 61 9200
0 28 2
52 35 1
91 12 9472
87 13 9334
34 39 9308
9 50 9342
54 84 1
43 82 1
38 29 9287
37 69 9409
57 89 9775
70 56 1
13 26 ...

output:

379160

result:

ok single line: '379160'

Test #36:

score: 10
Accepted
time: 0ms
memory: 3828kb

input:

93 91 2
61 20 1
39 5 1
80 55 2
37 10 1
58 61 1
81 58 2
85 91 1
45 86 1
70 57 1
79 18 1
44 29 2
41 76 2
43 25 1
55 78 1
88 34 1
69 9 1
9 68 1
6 81 1
28 13 1
31 11 1
1 52 1
53 27 1
18 28 2
67 0 1
47 22 1
20 92 1
26 37 1
0 7 1
12 14 1
30 56 1
64 46 1
23 32 2
52 72 2
4 31 2
78 28 2
40 39 2
27 47 2
84 74...

output:

62

result:

ok single line: '62'

Test #37:

score: 10
Accepted
time: 1ms
memory: 3900kb

input:

96 94 1
90 85 1
84 44 2
34 55 2
41 33 2
55 56 2
57 86 2
35 31 2
91 10 1
3 45 1
10 16 1
30 0 2
95 2 2
44 36 1
87 92 1
13 42 1
29 25 2
27 41 2
73 66 1
86 5 2
74 79 2
58 94 1
88 34 2
40 0 2
53 86 2
7 61 1
28 73 2
5 81 1
26 0 1
18 29 1
56 60 2
61 86 1
31 91 1
65 40 2
77 0 1
92 7 2
50 0 1
23 51 1
20 3 1
...

output:

69

result:

ok single line: '69'

Test #38:

score: 10
Accepted
time: 0ms
memory: 3836kb

input:

96 94 3
53 94 2
43 0 1
48 38 2
63 45 2
94 30 2
44 62 2
68 48 1
7 49 9682
91 9 2
1 49 9198
22 60 2
10 18 9935
29 4 1
41 49 9497
13 37 2
24 18 9689
23 60 2
40 28 1
54 28 2
55 48 2
16 27 1
75 26 9348
79 0 1
62 30 2
0 55 1
37 20 1
57 49 9892
58 49 9492
25 14 2
66 49 9382
14 0 1
73 9 1
77 49 9029
61 49 9...

output:

39319

result:

ok single line: '39319'

Subtask #3:

score: 23
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #39:

score: 23
Accepted
time: 35ms
memory: 12140kb

input:

100000 99998 1
73582 96282 10000
35963 23848 2
5713 72835 4
6874 20414 4
50543 28033 4
20995 55616 1
28454 29051 4
40648 48155 3
64932 53061 5
23132 78085 5
32818 67850 5
71252 64368 3
5513 17347 5
71183 88789 1
23480 38494 3
82357 32531 2
12449 31086 5
21205 20378 5
94059 8357 3
95706 21775 4
18702...

output:

10296

result:

ok single line: '10296'

Test #40:

score: 23
Accepted
time: 36ms
memory: 11964kb

input:

100000 99998 1
59639 24419 4
70770 99487 2
83963 65965 1
43146 51842 10000
57454 83807 1
34990 38445 5
61838 4285 1
74391 84892 3
18975 10591 3
26745 37805 1
19923 89957 3
19609 61247 2
76936 97666 5
8502 17003 2
83352 22721 3
13738 84501 2
25371 55692 4
26250 66645 5
45497 62148 1
97142 3630 2
9652...

output:

10297

result:

ok single line: '10297'

Test #41:

score: 23
Accepted
time: 30ms
memory: 12188kb

input:

100000 99998 10000
76129 3648 7
4960 3856 9
74692 93734 7
11819 16964 1
97365 11231 4
34256 60391 4
12767 1594 4
62290 95017 2
86545 62095 1
64129 73270 4
51233 42002 6
58877 8070 1
31479 43750 1
18333 98252 4
16751 66480 5
72305 84226 10
28784 88535 6
94434 5267 7
94749 97528 4
89314 75765 2
70460 ...

output:

16303

result:

ok single line: '16303'

Test #42:

score: 23
Accepted
time: 30ms
memory: 11860kb

input:

100000 99998 10000
39397 6699 5
58810 22486 6
23232 37840 10
18549 30348 6
5076 38314 10
31298 46500 6
49306 25544 7
37344 76498 10
30648 44590 4
76581 47919 3
79495 73477 1
19142 59119 7
23854 20399 6
39873 41059 8
3244 23822 7
1488 99586 8
73196 99425 3
57047 18969 10
21556 93078 8
92808 43926 6
9...

output:

18051

result:

ok single line: '18051'

Test #43:

score: 23
Accepted
time: 28ms
memory: 12152kb

input:

100000 99998 1000
26158 22503 311
55994 52564 866
7116 24809 258
42605 42912 424
94176 91161 129
28880 3748 736
93134 93338 275
96096 22476 488
27132 40639 35
91784 723 902
71068 96207 638
16198 26818 43
26451 37146 658
34394 37084 931
3251 43500 143
28156 84784 299
60540 81950 256
52660 52684 777
7...

output:

169010

result:

ok single line: '169010'

Test #44:

score: 23
Accepted
time: 31ms
memory: 11868kb

input:

100000 99998 1000
66013 66989 718
98915 57591 143
99056 72111 8
48075 51871 548
88907 66343 485
63686 50090 515
79705 36745 749
23037 84769 432
8314 88445 342
80201 51918 499
55151 64074 114
31304 63968 46
26139 77610 920
13798 78984 614
41970 60351 917
55258 21403 521
55120 35753 256
10402 83414 40...

output:

144907

result:

ok single line: '144907'

Test #45:

score: 23
Accepted
time: 30ms
memory: 12004kb

input:

100000 99998 10000
0 97541 10000
99999 92292 3
99998 1881 7
25137 92279 8
99997 73994 7
99995 31156 7
68411 15463 10
99994 65727 10
99992 24863 4
99939 97044 6
99991 77218 9
99989 15644 8
99988 72315 6
99987 54822 1
99986 43106 4
99985 9761 1
99984 64002 4
15860 56339 1
99983 99666 1
99981 7327 5
99...

output:

30000

result:

ok single line: '30000'

Test #46:

score: 23
Accepted
time: 35ms
memory: 11880kb

input:

100000 99998 10000
0 51968 10000
99999 26950 4
99998 97844 9
99997 64485 7
99996 75107 2
99995 82450 5
3748 6424 6
88271 9793 1
99994 62801 7
99991 24639 2
75054 81575 8
69490 38652 10
27262 24749 3
99990 32689 8
99986 47042 5
83413 73473 8
99985 90514 7
99983 21328 7
99982 94061 4
2749 83512 5
6868...

output:

20000

result:

ok single line: '20000'

Test #47:

score: 23
Accepted
time: 34ms
memory: 12004kb

input:

100000 99998 10000
0 94088 532
99999 69808 777
99998 9819 1264
99997 55524 7185
99996 88412 4754
8638 58564 6661
31460 61496 8877
99995 91857 7566
99992 29591 6507
99991 23248 792
99990 92650 2821
10547 60199 8491
99989 17799 9659
99987 45059 3063
99986 8342 106
31073 53944 2049
99985 61753 9364
999...

output:

299750

result:

ok single line: '299750'

Test #48:

score: 23
Accepted
time: 32ms
memory: 12004kb

input:

100000 99998 10000
46044 91191 9994
10700 2843 4004
0 27848 1374
99997 59419 86
99996 43562 6385
29531 60954 584
99995 25757 2490
99993 66943 1277
61259 53025 705
58917 92575 5200
13442 43734 7327
99992 9962 6669
99988 52504 9262
88693 58 5117
3615 79195 678
99987 82717 4525
99984 41832 807
99983 53...

output:

284124

result:

ok single line: '284124'

Test #49:

score: 23
Accepted
time: 35ms
memory: 11968kb

input:

100000 99998 10000
64991 32817 10000
68054 48039 10000
63028 99668 8
60202 42906 3
38922 31192 6
90512 29537 5
75335 90791 4
85852 11129 8
3364 86926 10
91080 1198 1
43022 32190 3
59551 42268 5
38089 91583 2
22315 28793 1
36704 56263 6
35855 29234 10
4842 51169 6
50718 94018 8
49177 39071 10
14708 4...

output:

30019

result:

ok single line: '30019'

Test #50:

score: 23
Accepted
time: 31ms
memory: 12288kb

input:

100000 99998 10000
26503 84874 10000
30797 22437 3
37864 15658 10000
53537 19369 5
86367 25411 8
54848 3312 9
91278 32237 2
78041 79571 1
89225 36528 3
83917 69917 4
63413 28736 1
96714 2863 10
982 82535 10
49277 64116 9
71090 96079 8
1470 12053 9
80408 50804 3
44000 41317 4
48896 23065 5
69899 8831...

output:

30039

result:

ok single line: '30039'

Test #51:

score: 23
Accepted
time: 33ms
memory: 11856kb

input:

100000 99998 10000
10504 59058 6924
32173 97970 3986
71739 85422 1962
49219 62994 5268
28035 18440 1063
46708 72172 9660
21298 10936 8654
70529 60003 8743
49139 40140 3732
54829 12950 7859
97867 76611 7295
94275 70449 3065
10383 73369 6000
81169 95875 9905
26200 72176 2306
79267 60428 6158
43911 362...

output:

9893392

result:

ok single line: '9893392'

Test #52:

score: 23
Accepted
time: 30ms
memory: 11860kb

input:

100000 99998 10000
40907 84672 4638
56745 79929 6661
85382 69428 8549
96430 41078 2034
58442 53255 9398
41088 18248 3499
36090 55699 1848
14852 97336 5342
17256 56497 5328
76037 49570 5757
94607 90253 9239
1623 68269 9880
59418 98562 2892
98929 33338 6447
32315 49198 5704
2525 33436 4060
296 78445 1...

output:

7224462

result:

ok single line: '7224462'

Test #53:

score: 23
Accepted
time: 1ms
memory: 4388kb

input:

3000 2998 1
1159 2575 5006
1143 2034 1
579 2090 2
137 1427 4
2754 2971 2
2689 1131 2
900 1880 4
2652 1387 2
243 2545 3
1063 1789 2
1355 1088 3
1558 12 4
293 2973 2
887 1702 5
1754 652 1
1439 2629 2
1196 1717 4
2594 418 1
1053 1853 2
1157 328 2
1083 1197 1
1741 68 1
2435 210 2
2141 2132 4
1415 303 2
...

output:

5569

result:

ok single line: '5569'

Test #54:

score: 23
Accepted
time: 1ms
memory: 4104kb

input:

3000 2998 1
968 1603 7207
2753 2248 2
652 1140 1
1705 1851 4
152 2086 5
1349 265 5
851 2387 4
1987 438 5
2234 2753 5
2468 2669 3
2202 734 5
2201 2705 5
126 271 1
2142 2017 4
1265 378 4
2108 160 4
618 2633 2
125 925 5
439 805 4
1427 2104 1
2464 2682 3
2918 825 5
822 1018 2
328 1984 2
706 2765 3
1717 ...

output:

7816

result:

ok single line: '7816'

Test #55:

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

input:

3000 2998 1000
668 2791 436
1142 671 268
44 98 67
2183 2107 834
852 1709 728
1861 1620 860
21 900 950
42 967 480
511 1516 324
24 1974 733
749 2353 116
1221 302 674
2398 945 970
1413 238 253
219 1755 526
177 662 167
2631 1722 186
837 1119 461
2742 1826 893
1082 1126 760
1345 1819 35
2565 2742 517
381...

output:

49241

result:

ok single line: '49241'

Test #56:

score: 23
Accepted
time: 1ms
memory: 4092kb

input:

3000 2998 1000
1530 1465 717
1169 607 680
791 559 720
1794 583 965
2594 1007 724
1403 1742 59
1039 232 817
1526 2900 965
270 725 887
2782 2520 970
17 1061 431
733 2252 984
2518 1237 871
820 2976 525
1387 2461 483
275 721 20
18 1972 13
1499 905 329
786 930 375
1532 922 138
2194 2558 519
1286 2542 599...

output:

40988

result:

ok single line: '40988'

Test #57:

score: 23
Accepted
time: 1ms
memory: 4136kb

input:

3000 2998 2797
996 109 1
805 2091 10000
2216 2897 1
2982 2418 10000
871 1874 10000
1126 1390 1
1999 1465 1
1756 348 1
514 2203 1
1433 1579 10000
76 415 10000
577 1135 10000
550 935 1
2328 2890 10000
1096 981 10000
1573 1589 1
1219 2003 10000
138 1113 10000
1060 882 10000
2395 1792 1
2977 228 1
1241 ...

output:

350016

result:

ok single line: '350016'

Test #58:

score: 23
Accepted
time: 1ms
memory: 4400kb

input:

3000 2998 980
1278 976 1
2212 102 1
1206 1257 10000
340 1787 10000
2927 2954 1
1876 64 1
2017 1703 10000
1746 1498 1
202 609 10000
1947 1416 10000
1515 1534 1
2116 733 10000
2682 248 1
1805 466 1
220 2019 10000
2703 1001 10000
2753 2659 1
2265 1178 1
1666 1337 10000
914 1163 1
1505 1640 10000
238 25...

output:

340021

result:

ok single line: '340021'

Test #59:

score: 23
Accepted
time: 1ms
memory: 4092kb

input:

3000 2998 5336
1940 2835 3002
2536 2867 3001
2814 1744 3002
503 1581 3000
665 787 3002
2735 2807 3001
1733 2196 3001
2289 883 3000
433 274 3000
265 619 3002
2669 1525 3002
1502 2696 3002
2463 842 3002
645 680 3001
2536 2508 3001
1471 346 3000
1944 50 3000
2414 259 3000
2877 1573 3000
291 2827 3001
2...

output:

519159

result:

ok single line: '519159'

Test #60:

score: 23
Accepted
time: 1ms
memory: 4148kb

input:

3000 2998 7356
2774 1150 3001
1982 857 3002
2419 1013 3002
1129 113 3001
77 2932 3002
1880 2069 3002
1778 1154 3001
2258 2044 3002
1306 1655 3000
1897 2130 3001
1829 543 3000
2426 1574 3002
807 2263 3001
2318 623 3000
745 2370 3000
2123 1378 3000
63 1846 3000
2491 2311 3001
1926 294 3002
109 1943 30...

output:

474193

result:

ok single line: '474193'

Test #61:

score: 23
Accepted
time: 33ms
memory: 12060kb

input:

100000 99998 1
86594 44998 10000
2656 78348 5
29361 1084 1
14686 33265 5
58944 91007 5
93485 5167 2
58065 11945 1
47718 96176 1
12466 5548 4
4718 25583 5
19049 54430 1
24177 54306 3
6604 32050 2
5384 44573 5
27753 95433 4
44337 70918 1
75101 54120 2
10272 15460 2
76931 89159 3
17520 58817 4
87199 77...

output:

13029

result:

ok single line: '13029'

Test #62:

score: 23
Accepted
time: 32ms
memory: 12096kb

input:

100000 99998 1
63302 50579 1
30305 49159 10000
11496 24081 3
17934 77122 1
50693 18354 4
58861 75368 1
97739 46117 2
11773 96142 3
85370 9268 4
40890 601 1
88170 94192 3
52663 83139 1
78745 43747 5
22833 12899 2
1747 11754 2
23728 55692 1
13420 12016 5
14785 25729 5
35048 73156 2
51596 71750 3
27429...

output:

13172

result:

ok single line: '13172'

Test #63:

score: 23
Accepted
time: 32ms
memory: 12040kb

input:

100000 99998 1000
97599 96245 824
49220 69435 839
97964 97536 91
95051 21909 595
70210 3741 808
2138 90100 239
45609 42059 321
36097 61145 527
81848 54116 900
97110 23123 661
64508 98451 243
46614 58938 713
58723 37309 587
7182 1460 218
76206 2448 621
71253 94503 378
93130 97220 780
98903 7161 893
9...

output:

156792

result:

ok single line: '156792'

Test #64:

score: 23
Accepted
time: 29ms
memory: 11932kb

input:

100000 99998 1000
56643 51303 907
19902 57082 959
47811 40560 170
95200 13184 266
6562 79751 475
88776 19923 769
23215 48545 236
39537 90724 748
23885 87378 8
40514 68442 796
66522 59981 658
38761 82373 79
19771 42259 866
90287 63260 350
59610 63432 556
76393 76743 49
992 23396 41
42161 58070 153
41...

output:

156423

result:

ok single line: '156423'

Test #65:

score: 23
Accepted
time: 1ms
memory: 3988kb

input:

2365 2363 2
2073 2148 2
973 1772 1
1211 815 2
1666 989 1
1390 1324 2
1835 217 2
1763 2346 1
89 2199 1
67 2199 1
1996 2121 1
206 972 2
1830 1743 1
1688 429 1
262 588 2
2192 1153 1
908 2121 1
2230 2148 1
1773 2148 1
894 529 2
1375 483 2
1911 529 2
2026 1199 1
525 510 1
2033 238 1
1240 1588 1
2251 195 ...

output:

16

result:

ok single line: '16'

Test #66:

score: 23
Accepted
time: 1ms
memory: 4304kb

input:

2105 2103 7
1740 1823 2
1956 1861 2
22 1310 2
625 1861 1
1017 212 2
1053 1933 1
2053 1278 9342
224 1141 2
104 413 1
1980 1116 1
1401 1956 1
52 413 1
1905 1636 2
1348 1078 2
1488 212 2
1340 474 2
1008 53 1
704 1921 1
2026 1306 2
1233 713 9462
939 413 2
227 789 9003
776 212 1
2078 1199 2
1624 1956 1
4...

output:

914061

result:

ok single line: '914061'

Test #67:

score: 23
Accepted
time: 1ms
memory: 4048kb

input:

2395 2393 2
1445 774 2
6 544 1
865 1486 1
2320 1290 1
326 2314 2
2394 2098 1
1702 1808 2
2322 2098 1
2122 81 1
623 2236 1
2274 1573 2
338 1901 2
189 1542 2
1456 147 1
568 1678 1
2058 1725 1
738 296 1
1628 1622 2
949 1474 1
1208 1573 2
744 1573 2
2242 2036 1
1859 954 2
1675 537 2
1578 1008 1
2339 117...

output:

198

result:

ok single line: '198'

Test #68:

score: 23
Accepted
time: 1ms
memory: 4128kb

input:

2590 2588 4
909 606 1
1061 2009 1
1083 2344 2
1272 1057 1
1396 1469 2
96 680 2
1071 1741 1
434 1414 1
553 667 1
2063 2433 2
182 1141 1
2496 2345 1
1073 2415 2
1996 381 2
1036 2021 2
2512 1807 1
1840 5 1
1261 1867 2
1353 341 1
2148 1644 2
561 1116 1
2464 1821 2
663 956 2
512 1878 2
2224 839 1
1919 12...

output:

202

result:

ok single line: '202'

Test #69:

score: 23
Accepted
time: 1ms
memory: 4136kb

input:

2627 2625 9
110 1583 1
906 1655 2
218 1743 1
1521 416 1
527 980 1
2421 179 1
888 1185 1
469 2055 1
1747 309 1
1065 2449 1
1118 523 2
661 926 2
630 1834 1
1362 1094 1
1392 35 2
1055 617 1
1976 448 1
2037 1219 1
1078 26 2
633 980 2
930 902 1
2527 278 2
321 744 1
331 903 2
2433 980 1
1410 1643 1
1507 1...

output:

171

result:

ok single line: '171'

Test #70:

score: 23
Accepted
time: 1ms
memory: 4056kb

input:

2598 2596 9
327 60 2
2285 60 2
1830 60 1
1160 1407 2
2355 1973 1
1186 111 2
1689 253 2
1843 2561 1
1070 2094 1
1455 2485 1
2526 2441 1
300 2388 1
1230 2323 1
1232 671 2
1657 2156 1
2099 1753 2
1817 117 1
333 2191 1
1056 208 2
474 1112 2
2400 2588 2
2451 441 2
1379 2424 2
72 1724 2
115 2366 1
755 232...

output:

184

result:

ok single line: '184'

Test #71:

score: 23
Accepted
time: 1ms
memory: 4060kb

input:

2593 2591 9
2245 2002 2
1482 175 1
215 405 9500
1719 2355 9590
1089 2327 9033
2290 1695 2
452 1383 1
327 169 9777
812 974 9968
1686 1014 9654
1221 261 9768
1870 1247 9654
432 394 1
2293 1565 2
763 689 1
1775 821 9750
1169 2334 9168
1239 1419 1
2512 2055 9987
1204 2259 9308
1217 1212 2
503 1607 2
286...

output:

1219480

result:

ok single line: '1219480'

Test #72:

score: 23
Accepted
time: 1ms
memory: 4128kb

input:

3000 2998 5
2383 2985 9209
2973 2929 1
1667 2915 2
2985 912 9469
15 2531 9172
1710 2650 1
28 2733 1
1892 1710 2
335 927 1
2634 2440 2
1421 2841 2
918 1730 1
835 104 2
485 630 1
1914 2924 9915
658 1172 2
1891 1347 1
1915 2427 2
2238 1348 1
1890 2976 1
1161 228 2
1338 1240 2
602 1555 1
2749 122 9637
7...

output:

854596

result:

ok single line: '854596'

Test #73:

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

input:

2751 2749 1
2233 544 9121
2724 108 9662
701 638 9656
1686 1152 9297
2076 2744 9252
1194 525 1
2004 1353 9703
1777 1717 2
1794 1542 9439
2297 2076 9124
1534 2223 1
1868 2052 9954
29 519 9378
96 838 9791
1582 1421 9227
2691 1227 9338
710 1100 9853
538 1546 9895
892 1008 2
83 2113 9395
907 1160 9962
67...

output:

313490

result:

ok single line: '313490'

Test #74:

score: 23
Accepted
time: 1ms
memory: 4020kb

input:

2648 2646 6
1257 984 9723
1460 516 1
2411 2496 1
2194 2074 2
706 62 1
586 1561 9653
1304 861 9925
2265 1052 2
1046 1735 1
2592 51 2
1341 1547 9472
104 1688 9919
2150 1601 9106
739 1688 9214
2209 128 1
506 356 2
980 2418 1
523 1093 1
2078 2643 2
1272 2215 1
747 1601 9650
1736 221 9299
2290 53 1
2537 ...

output:

68075

result:

ok single line: '68075'

Test #75:

score: 23
Accepted
time: 33ms
memory: 17440kb

input:

100000 99998 7119
11589 21861 6748
54109 60361 7914
34709 23654 3420
5575 15320 1727
72767 50350 5498
49722 21483 5369
6975 96662 3553
38783 70286 1427
9231 70739 4305
11560 22281 8204
27165 6390 2845
53295 26968 1650
54538 6688 9875
7763 77289 9988
79945 32827 7893
43756 89912 1394
32086 10961 9750...

output:

501069463

result:

ok single line: '501069463'

Subtask #4:

score: 18
Accepted

Test #76:

score: 18
Accepted
time: 16ms
memory: 9016kb

input:

93596 31195 86
4343 1589 8
61155 92883 5
91917 6571 5
32506 33054 1
65199 80366 4
71048 12809 2
32716 43004 9
90865 57094 9
9813 23701 10
45224 84405 5
16380 16918 8
82115 65429 7
80306 41444 6
40398 257 4
61527 7638 9
20232 39859 2
8528 84042 4
21217 74039 5
39362 88045 10
17829 47708 6
5739 10629 ...

output:

19379

result:

ok single line: '19379'

Test #77:

score: 18
Accepted
time: 16ms
memory: 8992kb

input:

94019 31406 100
85763 45221 1
50486 28280 7
46677 13819 3
70617 68054 9
21237 73999 3
39789 22182 10
68879 30590 5
6184 3112 6
23597 13409 2
39520 33645 3
867 14256 2
77067 58515 7
66472 64896 2
81572 4897 8
44918 36960 1
72925 1410 1
86679 52082 2
56784 42467 2
15214 78347 1
70135 45114 7
7031 6547...

output:

18210

result:

ok single line: '18210'

Test #78:

score: 18
Accepted
time: 17ms
memory: 8992kb

input:

93576 31189 100
33690 5606 7
41314 61532 6
93033 46959 7
67939 29038 10
44450 1857 10
19542 53125 1
6457 10475 7
70306 32254 1
42872 26031 2
67209 35451 8
56858 20079 10
52076 71588 5
11495 80250 10
14163 68833 10
71396 31514 2
56731 21951 6
10842 61644 2
33996 30411 5
14905 82317 9
21202 19654 8
60...

output:

18210

result:

ok single line: '18210'

Test #79:

score: 18
Accepted
time: 17ms
memory: 8968kb

input:

94086 31266 100
25636 57346 10
94079 24151 10
4463 32738 10
41541 77810 3
33602 53397 6
18966 76056 2
66361 12208 4
39709 77536 5
41427 57844 2
4863 86799 9
35858 22037 1
53850 38127 6
79252 4318 2
31672 44347 4
4309 50164 7
66225 40792 9
87013 66449 2
69704 82679 9
31951 26541 3
57232 51720 2
24542...

output:

18210

result:

ok single line: '18210'

Test #80:

score: 18
Accepted
time: 8ms
memory: 9028kb

input:

93299 31137 64
82120 78282 8
12312 88502 4
23765 30782 9
61188 23903 5
39729 8863 8
12339 45915 3
82979 31464 1
64661 60465 6
16723 9921 3
86373 45725 2
40283 51744 7
45783 87210 9
63544 14217 1
66631 27499 7
79492 45867 9
38505 21219 1
6585 41935 5
16061 44303 1
13743 42311 9
41269 72316 1
84975 83...

output:

19457

result:

ok single line: '19457'

Test #81:

score: 18
Accepted
time: 10ms
memory: 9392kb

input:

99191 33153 66
60094 49511 9
32598 59409 10
40466 16529 1
43562 84030 5
35474 32281 1
79654 98751 9
4704 89588 9
10230 49901 6
70118 78054 6
7584 70179 6
92294 61004 4
87138 28053 1
21349 64864 1
26872 5584 1
73824 70732 4
83517 30122 2
57034 2158 6
45127 69481 1
57381 38841 5
73096 53854 8
55760 71...

output:

19674

result:

ok single line: '19674'

Test #82:

score: 18
Accepted
time: 17ms
memory: 9356kb

input:

98109 32707 100
88391 59001 10
85763 4703 5
58738 31197 1
27314 20836 8
6265 53032 3
4408 42705 4
57450 58093 7
21500 69129 5
79967 33125 6
13428 31146 9
12311 48176 10
45437 51374 1
65223 97390 8
19657 27090 10
29717 28820 4
56073 48475 10
22714 64306 10
4143 48834 9
78697 59684 8
51596 58546 4
351...

output:

18210

result:

ok single line: '18210'

Test #83:

score: 18
Accepted
time: 15ms
memory: 8764kb

input:

92053 30615 100
27450 39956 3
76183 46923 4
85224 18337 1
42483 63678 8
85241 84289 3
37001 80578 1
6157 68880 1
12929 20849 2
35287 13626 7
49370 87411 3
49736 373 4
11970 21859 5
15647 17331 7
45429 64483 3
7740 33987 6
59158 23897 4
60956 47289 8
73799 89971 8
15871 27615 5
51428 81392 7
79993 30...

output:

18210

result:

ok single line: '18210'

Test #84:

score: 18
Accepted
time: 16ms
memory: 8676kb

input:

91342 30431 100
35914 51317 7
82768 31530 5
14560 21103 10
62256 65155 5
76124 22684 9
10877 9350 10
740 25815 2
74091 17287 8
50054 15815 10
78307 32482 5
74602 77621 3
69751 3238 8
49677 61248 3
22080 60072 8
89199 30458 8
63202 41702 4
33611 26492 4
22548 6835 3
85686 1089 4
8567 30082 4
52372 88...

output:

18210

result:

ok single line: '18210'

Test #85:

score: 18
Accepted
time: 13ms
memory: 9056kb

input:

97116 32298 22
86740 85547 6
12524 82145 9
13982 45912 3
69833 2113 2
64081 42556 7
17952 25611 6
77424 6950 5
22104 69746 1
88883 86865 5
36515 84941 10
63227 44812 4
93371 49627 4
7755 71195 6
30379 93730 4
70413 83824 5
88448 4012 1
42434 102 4
3553 96342 5
22144 14546 7
77503 51910 6
71796 95222...

output:

19389

result:

ok single line: '19389'

Test #86:

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

input:

100 5 10000
95 73 1667
98 34 3851
64 7 2414
49 55 7129
52 43 4781

output:

28632

result:

ok single line: '28632'

Test #87:

score: 18
Accepted
time: 5ms
memory: 7180kb

input:

100000 281 10000
1493 10124 7257
6577 23934 7800
80044 48420 9247
23049 32450 4729
12043 84776 1758
68628 60163 602
39190 1345 642
5696 40836 3551
30849 66278 3902
97926 67302 1839
57228 53349 2656
59435 41037 599
61819 5278 5999
94523 98810 2074
90136 33555 6758
62494 14785 5498
56388 98613 8921
53...

output:

39787

result:

ok single line: '39787'

Test #88:

score: 18
Accepted
time: 5ms
memory: 7064kb

input:

100000 517 10000
27179 73293 4954
59239 62607 856
69932 33838 2108
42238 55232 5680
93705 74227 5852
23484 32618 2763
52363 99069 7879
87785 92586 9945
32891 30513 4517
16219 54242 1197
37676 37403 1934
32677 16186 9880
63949 10629 1780
49611 87478 2314
67323 12173 6050
98352 52890 3519
39138 26549 ...

output:

39924

result:

ok single line: '39924'

Test #89:

score: 18
Accepted
time: 2ms
memory: 7056kb

input:

100000 272 1
51296 93166 2
55894 42543 2
55247 84052 5
46417 37673 4
56657 19978 4
64093 70115 4
79951 72667 4
78976 6520 5
92521 62138 1
70645 52424 5
15156 55648 5
3165 21430 5
84233 59051 4
378 8163 2
43005 73070 1
58274 57988 2
22821 37886 5
34758 79663 1
12477 8240 4
46864 718 1
47783 21961 1
8...

output:

18

result:

ok single line: '18'

Test #90:

score: 18
Accepted
time: 5ms
memory: 7204kb

input:

100000 333 1
15873 42176 3
7148 76639 3
36245 12767 4
4152 81536 3
60005 57763 1
38928 47669 3
95794 69783 3
47971 58682 2
49308 52715 2
69695 67346 5
6539 4293 2
7979 37366 4
33291 24925 4
63274 71306 1
67116 61636 5
87924 32542 3
1797 27901 3
71824 47742 5
32009 63279 5
91331 98107 5
7713 90232 5
...

output:

18

result:

ok single line: '18'

Test #91:

score: 18
Accepted
time: 5ms
memory: 7064kb

input:

100000 206 12
16920 81037 8
37426 76749 10
46911 88529 6
25449 45496 4
51237 94507 5
52417 16829 7
51932 96928 10
68615 4269 6
50545 86734 3
84918 87098 3
13887 58345 1
4361 67943 8
48658 81903 3
99426 96159 5
96436 95110 8
71189 72971 3
45114 30050 6
46332 15556 4
30335 88465 1
54128 56178 1
60338 ...

output:

44

result:

ok single line: '44'

Test #92:

score: 18
Accepted
time: 5ms
memory: 7128kb

input:

100000 36 12
53191 12906 3
93739 42305 6
55136 9799 3
75691 27891 3
43996 32824 10
68278 44146 7
86885 58322 3
72999 2115 6
87767 64035 8
11175 78070 7
16033 38049 10
11063 39799 1
68928 77988 10
70272 3530 8
48667 96586 6
10525 97079 7
68526 14203 6
7215 77824 2
23624 97713 8
74042 30388 3
67686 41...

output:

44

result:

ok single line: '44'

Test #93:

score: 18
Accepted
time: 5ms
memory: 7172kb

input:

100000 723 10000
24550 30030 8612
80725 11889 551
21141 15508 6717
65893 2745 8750
76233 43785 4579
24577 88600 551
59715 20923 5726
53381 34634 5296
35550 51432 5926
50839 69582 895
78813 46420 7785
52157 73029 2027
39940 45611 2012
35962 47767 5254
93651 1190 6118
66850 15248 78
75865 73483 3447
6...

output:

39957

result:

ok single line: '39957'

Test #94:

score: 18
Accepted
time: 5ms
memory: 7056kb

input:

100000 214 10000
96155 21707 2412
95688 400 4791
32719 41586 9165
19842 99529 692
10776 68003 9737
47995 31365 6734
2999 55675 1656
97074 17603 1002
17186 5849 9041
67195 50299 5883
38286 12308 6424
27108 3485 7772
28675 7470 6814
96047 11746 8073
82909 42200 8131
34443 32443 4506
97815 80074 6277
6...

output:

39821

result:

ok single line: '39821'

Test #95:

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

input:

1 0 4427


output:

0

result:

ok single line: '0'

Test #96:

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

input:

3000 23 10000
2126 345 4039
1458 1033 1711
1503 1448 6825
351 551 4785
2284 2066 5658
2770 1013 9988
312 2839 575
57 500 4477
85 1104 1588
339 1343 4559
53 1146 627
2004 2541 1690
2302 292 6399
1678 1341 892
261 1713 2421
2274 1784 3910
2966 464 3613
2691 1203 4814
754 1712 8415
657 2821 2301
1558 1...

output:

35240

result:

ok single line: '35240'

Test #97:

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

input:

100000 229 10000
17607 878 3000
68408 89908 3000
41588 9068 3000
84776 32415 3000
47805 97546 3000
8453 47343 3000
47792 20057 3000
95960 4944 3000
64342 9256 3000
15565 57776 3000
73611 35310 3000
75063 33907 3000
68692 74042 3000
50887 72218 3000
88359 56760 3000
72428 30984 3000
82860 8638 3000
6...

output:

26000

result:

ok single line: '26000'

Subtask #5:

score: 12
Accepted

Dependency #2:

100%
Accepted

Test #98:

score: 12
Accepted
time: 1ms
memory: 3908kb

input:

1000 829 100
816 52 2
84 324 9788
859 442 6
794 157 9
533 680 9
84 926 9524
365 236 3
507 809 3
777 543 1
465 44 1
96 416 9
999 148 7
928 300 5
784 593 2
887 529 2
158 236 3
358 958 6
140 657 10
54 178 9
429 398 7
222 123 6
310 403 7
43 185 1
228 88 4
205 185 6
648 588 3
725 416 3
361 72 7
481 140 8...

output:

19935

result:

ok single line: '19935'

Test #99:

score: 12
Accepted
time: 0ms
memory: 4016kb

input:

2000 1668 100
1103 434 10
810 1713 6
1 334 7
481 616 5
765 1920 4
1855 1096 9373
1212 1658 8
599 777 5
1131 694 4
1702 512 3
1362 1602 5
244 745 8
1637 624 6
567 714 3
575 1283 2
363 434 9
934 699 5
1785 138 8
1855 533 9213
1897 1624 9
915 1983 1
650 1217 10
495 771 9
887 1397 1
1203 139 8
988 602 9...

output:

19978

result:

ok single line: '19978'

Test #100:

score: 12
Accepted
time: 1ms
memory: 4348kb

input:

3000 2504 100
608 2785 10
2786 42 5
963 654 9154
2612 248 3
372 2572 8
2300 2070 8
1128 1810 3
1963 2064 1
963 1991 9107
2137 1544 5
2986 146 1
963 1365 9142
963 1982 9628
1376 958 4
763 2018 1
246 2178 3
1202 514 9
1764 2757 5
963 2332 9108
1330 2713 4
1030 631 4
2617 2674 7
251 1604 1
2713 38 4
51...

output:

19997

result:

ok single line: '19997'

Test #101:

score: 12
Accepted
time: 1ms
memory: 4200kb

input:

1000 845 1000
540 787 5
71 403 4
838 980 10
50 85 5
556 815 1
788 336 5
818 561 7
484 409 3
187 806 5000
187 634 5000
674 38 6
318 934 5000
999 427 2
192 278 1
931 357 10
187 432 5000
678 271 7
300 456 8
203 158 10
40 210 8
922 229 9
488 357 7
789 865 7
392 602 6
729 113 8
66 463 10
318 701 5000
318...

output:

11000

result:

ok single line: '11000'

Test #102:

score: 12
Accepted
time: 0ms
memory: 4272kb

input:

2000 1701 1000
20 1472 5
212 188 5000
809 1090 9
18 929 5
799 1242 7
1295 213 8
467 1480 10
83 852 4
676 530 7
1077 60 6
675 775 5000
982 1013 8
1536 1662 4
675 1025 5000
1523 842 7
121 47 8
675 1103 5000
1560 215 1
212 1567 5000
133 54 10
572 1240 1
212 1172 5000
946 1856 1
1699 52 10
1474 1633 7
6...

output:

11000

result:

ok single line: '11000'

Test #103:

score: 12
Accepted
time: 1ms
memory: 4068kb

input:

3000 2567 1000
635 1648 6
1811 749 5000
1811 2601 5000
2751 2063 5
666 631 3
1352 1885 2
1811 1925 5000
624 401 4
1226 1848 5000
1811 2279 5000
265 2059 10
1379 2812 10
2598 995 4
175 1004 8
2642 2367 7
2680 44 4
831 206 5
1295 2302 7
1233 1040 9
2362 2059 8
1577 2495 10
1252 835 5
562 591 8
340 154...

output:

11000

result:

ok single line: '11000'

Test #104:

score: 12
Accepted
time: 0ms
memory: 3912kb

input:

1000 874 1000
742 670 5
173 536 5000
173 418 5000
685 133 10
297 615 8
962 252 3
162 747 10
864 782 10
173 171 5000
15 838 5
173 693 5000
65 670 10
173 316 5000
539 395 2
620 377 7
766 150 6
214 190 2
215 89 8
480 42 5100
549 9 4
939 648 1
173 768 5000
240 542 10
480 563 5100
407 558 5000
301 363 2
...

output:

12000

result:

ok single line: '12000'

Test #105:

score: 12
Accepted
time: 1ms
memory: 4024kb

input:

2000 1742 1000
51 910 5100
958 744 2
1453 35 3
1655 1452 9
20 460 2
1306 1231 5000
1442 1336 1
51 836 5100
1939 90 10
455 535 7
1078 1379 7
645 231 4
579 605 9
1033 96 4
1432 1312 6
1695 1476 5000
602 964 9
1695 125 5000
1122 961 1
548 1912 5
155 1046 9
51 1600 5100
998 1807 4
1306 287 5000
1053 710...

output:

12000

result:

ok single line: '12000'

Test #106:

score: 12
Accepted
time: 1ms
memory: 4064kb

input:

3000 2613 1000
1232 2753 5000
980 2788 8
432 1566 10
1451 1873 5000
1998 2818 6
856 1264 2
1293 136 7
1451 1654 5000
1451 417 5000
1451 849 5000
2461 2048 10
1232 1358 5000
948 464 8
1799 299 6
10 2808 9
925 72 6
85 1998 2
1451 713 5000
2510 285 5
1825 1774 3
1071 2653 4
1571 1900 6
2846 1282 4
711 ...

output:

12000

result:

ok single line: '12000'

Test #107:

score: 12
Accepted
time: 0ms
memory: 3796kb

input:

12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3

output:

18

result:

ok single line: '18'

Test #108:

score: 12
Accepted
time: 1ms
memory: 3828kb

input:

100 30 10000
32 30 1636
71 53 6318
25 42 9222
54 38 6034
86 72 7559
12 90 6694
22 23 3756
88 91 2573
69 43 6417
85 9 3184
35 65 6831
29 3 1761
62 6 6345
68 57 4083
37 21 4231
35 22 7839
14 76 6535
67 49 8915
98 8 1707
61 55 9820
93 81 4882
45 84 9943
54 55 6973
87 16 4978
46 28 1593
15 79 3336
66 33...

output:

44211

result:

ok single line: '44211'

Test #109:

score: 12
Accepted
time: 1ms
memory: 4188kb

input:

2932 2931 2928
1012 1110 6354
2494 2477 2910
762 2488 9102
1212 2068 9264
1636 2268 3721
1269 2401 9871
2831 1664 2929
2582 2627 8557
247 338 7865
2582 2333 683
2656 1929 2879
2158 1821 7855
48 59 6468
1698 981 1913
1352 290 8048
2297 1446 1762
613 2668 5661
628 2808 3488
1228 2061 590
2651 2751 652...

output:

14878564

result:

ok single line: '14878564'

Test #110:

score: 12
Accepted
time: 1ms
memory: 4204kb

input:

2888 2887 9635
2282 1917 7735
1731 1617 2076
336 1919 1760
1902 143 7340
441 102 1874
2605 541 6719
1107 2163 3735
2211 405 4712
2722 926 4625
1251 1610 7903
531 97 3681
235 1823 1289
1868 2805 7295
2432 343 5409
1510 1785 6197
822 1692 8506
1476 2111 4078
1645 1285 9344
2762 2519 7044
1252 2184 126...

output:

14237224

result:

ok single line: '14237224'

Test #111:

score: 12
Accepted
time: 0ms
memory: 4108kb

input:

3000 1677 1
2401 1279 5
1957 2286 5
1977 238 2
2513 2427 3
2521 1596 1
254 1992 1
1275 580 2
2869 263 5
538 336 5
914 1634 1
686 254 4
2066 1908 2
1937 348 4
1921 1087 5
2384 1740 3
1341 1347 2
1189 54 3
1533 2398 3
1814 2691 2
2097 636 3
183 1167 1
677 1282 4
1358 2676 2
1273 850 4
713 1495 3
925 2...

output:

66

result:

ok single line: '66'

Test #112:

score: 12
Accepted
time: 0ms
memory: 3984kb

input:

3000 605 1
667 54 2
1415 631 1
1692 1279 1
441 1688 4
2791 475 4
2652 1693 5
66 34 1
517 219 2
1806 1695 4
677 878 5
2460 2597 5
372 2953 2
802 1236 3
398 389 5
1931 58 3
1734 93 2
975 2015 2
968 1421 3
17 2035 5
535 2640 3
1160 1652 2
882 2218 4
2139 2277 5
1595 1121 1
659 768 1
2790 1423 5
839 262...

output:

34

result:

ok single line: '34'

Test #113:

score: 12
Accepted
time: 1ms
memory: 4072kb

input:

3000 1272 47
749 2440 3
1578 2659 7
1432 594 2
551 1549 8
1913 2176 6
1159 249 6
2838 935 10
2847 499 9
1367 2514 1
1469 2670 1
2025 293 2
58 1615 6
530 2486 10
841 1052 7
1001 2222 5
2575 1986 9
325 2683 10
2232 737 1
951 2601 3
2439 28 5
2764 1806 7
1761 2860 6
2700 2284 3
2108 1830 3
909 1489 2
2...

output:

137

result:

ok single line: '137'

Test #114:

score: 12
Accepted
time: 1ms
memory: 4304kb

input:

3000 825 53
2350 2571 4
1278 153 6
579 286 9
1345 96 7
80 2681 2
491 425 1
1621 2959 7
494 1003 9
1565 2850 9
2533 2077 4
1268 2203 1
2123 733 5
1498 2176 9
2461 2636 5
2747 2770 6
1251 214 10
1673 2161 8
2881 994 3
53 2136 3
1744 2287 3
699 809 4
1409 1476 6
1368 2114 1
364 1701 2
706 2684 10
1419 ...

output:

146

result:

ok single line: '146'

Test #115:

score: 12
Accepted
time: 2ms
memory: 4160kb

input:

3000 2997 8283
1607 1245 4
712 1510 8
510 1950 5
2887 1833 7
1489 1386 3
2006 864 2
661 2521 8
131 2947 10
617 9 2
1184 521 3
1282 2299 10
1210 622 2
2358 299 4
2076 2011 8
637 1321 9
121 2747 2
700 997 7
731 717 8
812 1192 8
1755 1362 1
2771 664 10
2750 1979 3
968 2153 6
215 1759 9
2674 2472 5
2545...

output:

17203

result:

ok single line: '17203'

Test #116:

score: 12
Accepted
time: 1ms
memory: 4148kb

input:

3000 2997 10000
1002 160 4
415 1768 6
2375 2296 10
1715 446 7
1097 2053 1
365 1173 1
513 613 7
2788 2130 8
1986 2108 5
2619 1358 7
1580 2986 2
2955 115 5
1665 832 1
483 2443 7
940 1549 9
2981 700 1
2064 328 7
2314 1463 2
1262 1686 2
2964 2203 8
1418 2948 4
2320 2175 5
20 775 1
1319 1555 1
2674 2564 ...

output:

20507

result:

ok single line: '20507'

Test #117:

score: 12
Accepted
time: 1ms
memory: 3968kb

input:

3000 237 989
1991 1675 757
2873 2082 638
544 965 757
2397 728 867
1537 1970 17
1586 2425 280
660 2072 888
807 1544 176
916 709 50
633 450 946
2282 969 263
1880 2423 542
1972 1950 414
2478 1858 837
417 19 12
1985 2058 849
2688 370 444
1635 1522 165
295 2717 382
1768 2218 246
2564 167 573
2226 2601 64...

output:

3952

result:

ok single line: '3952'

Test #118:

score: 12
Accepted
time: 1ms
memory: 4300kb

input:

3000 1806 1000
382 2424 5
233 335 916
603 308 951
1437 1105 562
1208 106 871
1315 1490 870
1120 1237 954
2036 579 270
2677 2067 176
933 976 545
235 84 306
517 2836 925
1793 932 602
31 1570 289
218 1119 196
2150 1135 348
1762 228 287
2878 2253 810
323 278 973
2901 1129 241
2450 946 777
2983 1663 946
...

output:

6420

result:

ok single line: '6420'

Test #119:

score: 12
Accepted
time: 1ms
memory: 4340kb

input:

3000 1937 9146
2769 176 8735
2243 1754 9270
2016 791 8913
1381 2218 8882
1696 1582 9774
2906 81 8232
2578 1029 9751
2138 2073 8456
24 2166 9000
471 1258 8938
1710 2391 8857
2012 666 9343
2731 2352 9359
1863 1401 8850
2457 1413 9039
244 878 8024
670 2670 8316
96 164 8315
329 1047 9059
614 1790 9936
2...

output:

91855

result:

ok single line: '91855'

Test #120:

score: 12
Accepted
time: 1ms
memory: 4100kb

input:

3000 2045 4025
151 1341 9867
2541 987 9550
1004 380 9263
2596 2081 9137
165 1298 9943
2926 419 8724
1492 1196 9048
384 2375 8047
2163 1571 8157
2891 1140 8557
383 2300 8421
1606 349 9527
1376 850 8546
2593 1060 8915
1945 836 8498
260 1057 8676
2271 2653 9997
971 1204 9763
243 2811 8833
2463 68 9996
...

output:

101452

result:

ok single line: '101452'

Test #121:

score: 12
Accepted
time: 1ms
memory: 3988kb

input:

3000 1000 4422
262 1273 1
1612 2576 10000
193 2069 1
543 1311 10000
332 2584 1
1611 1121 1
2588 2210 10000
1924 186 10000
2960 150 1
594 1851 10000
473 2622 1
2129 1326 10000
2656 1254 1
1066 52 10000
2487 1009 1
1981 820 10000
1481 1069 10000
2501 213 1
1482 672 1
1996 2613 10000
2885 2896 1
490 33...

output:

54423

result:

ok single line: '54423'

Test #122:

score: 12
Accepted
time: 1ms
memory: 3992kb

input:

3000 1000 5856
856 2076 1
2146 425 10000
1598 983 1
2025 2384 10000
83 1696 1
2544 1888 10000
1185 2753 10000
1412 593 1
530 2112 10000
2180 2977 10000
1021 2561 10000
1826 998 10000
804 2852 1
895 2626 10000
67 647 10000
2114 2504 1
112 1692 1
1155 346 10000
1254 2404 10000
635 2478 10000
1652 1756...

output:

65857

result:

ok single line: '65857'

Test #123:

score: 12
Accepted
time: 1ms
memory: 4124kb

input:

3000 2804 32
620 1871 3001
1400 279 3000
891 2613 3000
1186 2861 3002
2470 2538 3001
1299 1891 3001
1650 2237 3002
1455 2256 3000
620 2674 3002
1548 2131 3000
601 2539 3001
856 1485 3000
471 2270 3001
2454 1760 3002
2587 1242 3001
1610 231 3002
527 2054 3001
2552 2729 3002
2194 2967 3002
112 23 3002...

output:

126048

result:

ok single line: '126048'

Test #124:

score: 12
Accepted
time: 1ms
memory: 4064kb

input:

3000 2847 4280
401 1821 3000
2083 2210 3001
511 2631 3001
147 2960 3000
2563 682 3001
2502 717 3000
302 944 3001
671 2492 3000
1633 2959 3001
2216 1406 3002
2788 2841 3001
2704 2208 3002
901 1918 3002
1995 189 3000
2036 2296 3000
1344 1920 3000
1972 1198 3002
405 1807 3000
257 2803 3002
2745 489 300...

output:

104588

result:

ok single line: '104588'

Test #125:

score: 12
Accepted
time: 1ms
memory: 3944kb

input:

3000 1000 1464
744 194 3000
384 597 3000
2602 2399 3000
2526 2742 3000
2220 1418 3000
875 2975 3000
128 167 3000
1662 2551 3000
227 330 3000
2970 1328 3000
2517 1320 3000
249 6 3000
2290 1608 3000
2198 843 3000
249 1746 3000
2977 1825 3000
766 1584 3000
2740 2980 3000
258 1073 3000
832 1197 3000
128...

output:

24000

result:

ok single line: '24000'

Test #126:

score: 12
Accepted
time: 1ms
memory: 4004kb

input:

3000 1000 9589
2121 1390 3000
1511 2974 3000
2102 536 3000
1727 1561 3000
631 1794 3000
2631 407 3000
1899 236 3000
248 2185 3000
372 1686 3000
1857 1986 3000
582 2878 3000
2342 1831 3000
2548 1834 3000
2881 1122 3000
764 1266 3000
749 2108 3000
277 504 3000
655 639 3000
2354 2460 3000
632 2353 3000...

output:

37178

result:

ok single line: '37178'

Test #127:

score: 12
Accepted
time: 1ms
memory: 4036kb

input:

3000 155 10000
1763 1316 328
21 996 6109
51 339 9689
774 2557 4270
1676 836 2835
1209 2438 9089
262 2393 1133
2388 842 5061
953 1304 1377
639 2373 7971
1022 2566 2335
2481 529 9083
1348 253 3906
729 1642 1610
633 2335 6428
2010 1054 3456
1679 1473 9365
268 2391 8117
2567 58 1071
1717 298 4181
2155 1...

output:

39563

result:

ok single line: '39563'

Test #128:

score: 12
Accepted
time: 1ms
memory: 4024kb

input:

3000 2638 1000
1387 2964 974
1734 2266 196
1246 2159 650
1061 1442 267
1112 2669 776
1339 2672 840
451 1099 287
576 139 939
1188 27 9
1732 649 131
2650 2606 415
2875 56 514
743 2684 776
505 2455 245
354 1485 739
2769 2516 272
2421 2883 877
770 2153 802
308 2589 648
590 2953 112
203 2469 991
2392 73 ...

output:

11441

result:

ok single line: '11441'

Test #129:

score: 12
Accepted
time: 1ms
memory: 4132kb

input:

3000 2685 1000
1171 1046 991
2349 2644 654
2565 1169 350
2828 2563 887
1165 1227 230
1488 2989 459
22 2526 892
1006 1017 199
1144 2776 447
1188 2058 783
1092 1084 116
2775 2665 990
2582 2349 19
2364 2603 254
519 655 385
998 2813 883
1213 1863 814
1288 1811 320
1339 1490 418
1539 784 42
899 2124 438
...

output:

11345

result:

ok single line: '11345'

Test #130:

score: 12
Accepted
time: 1ms
memory: 4280kb

input:

3000 1030 10000
170 1671 10000
0 1420 10000
2998 2584 10000
2997 1138 10000
2996 13 10000
2995 194 10000
1870 2415 10000
2994 116 10000
2992 1216 10000
2991 301 10000
2990 1479 10000
2989 2616 10000
763 1398 10000
2988 1529 10000
2986 2451 10000
2761 1447 10000
2985 839 10000
2983 136 10000
2982 229...

output:

40000

result:

ok single line: '40000'

Test #131:

score: 12
Accepted
time: 0ms
memory: 4260kb

input:

3000 251 10000
0 1866 10000
2999 861 10000
2998 406 10000
1865 565 10000
2997 129 10000
2995 2326 10000
2994 2105 10000
2993 359 10000
2992 1056 10000
2991 457 10000
2990 2651 10000
2989 2417 10000
2988 151 10000
2987 1541 10000
2986 2455 10000
2985 2863 10000
2214 2678 10000
2984 408 10000
2982 180...

output:

40000

result:

ok single line: '40000'

Test #132:

score: 12
Accepted
time: 1ms
memory: 4000kb

input:

3000 1913 10000
646 1456 8786
338 2744 6491
0 1710 6396
1333 1603 1238
2060 2043 83
1240 1208 6327
2997 711 462
2993 1025 5281
2992 2848 5890
2423 1859 2129
2991 1390 4544
2989 2883 6939
2988 1675 9143
2987 1145 2165
2986 430 8064
2985 2941 6016
2984 557 2869
2983 1571 8188
2982 1861 4689
2981 2754 ...

output:

158359

result:

ok single line: '158359'

Test #133:

score: 12
Accepted
time: 0ms
memory: 4052kb

input:

3000 2740 10000
0 264 2090
2999 1137 6354
2998 2154 9525
2997 2869 9579
2996 1107 5471
2995 1652 8135
2994 1693 3658
2993 2245 8675
2992 2789 6777
2991 1086 9259
2990 1981 7567
2989 182 4901
2988 193 2320
474 910 7547
2987 947 4713
2985 773 546
1290 853 4209
2984 2126 1976
2982 2979 5481
2981 2215 2...

output:

190565

result:

ok single line: '190565'

Test #134:

score: 12
Accepted
time: 0ms
memory: 4100kb

input:

3000 1852 10000
2562 2494 10000
2990 538 10000
1119 2974 10000
2155 397 10000
385 1935 10000
115 791 10000
640 1947 10000
2826 775 10000
2231 939 10000
144 1581 10000
351 1128 10000
1338 1547 10000
2016 89 10000
2092 379 10000
2573 1828 10000
18 228 10000
1726 1599 10000
1734 2161 10000
2373 1853 10...

output:

40031

result:

ok single line: '40031'

Test #135:

score: 12
Accepted
time: 1ms
memory: 4000kb

input:

3000 1701 10000
2057 152 10000
1297 2965 10000
2792 625 10000
312 2861 10000
2534 1092 10000
1902 2788 10000
1836 1020 10000
1194 996 10000
1682 2696 10000
2706 223 10000
1179 2019 10000
2977 1056 10000
1132 2290 10000
644 1544 10000
1396 2187 10000
544 2337 10000
453 151 10000
1943 2437 10000
612 1...

output:

40036

result:

ok single line: '40036'

Test #136:

score: 12
Accepted
time: 1ms
memory: 4016kb

input:

3000 1185 10000
209 1345 1849
44 730 7088
1595 826 1669
704 28 1528
312 2611 2182
2407 1250 4698
2584 2644 6318
1727 804 2251
1158 2817 2310
1950 1689 8646
1372 1714 5645
1058 2181 8086
2218 2828 8060
2948 2841 1310
1074 2885 7043
582 159 9653
1622 603 3046
1158 1770 7565
2184 1216 947
2762 979 8463...

output:

55431

result:

ok single line: '55431'

Test #137:

score: 12
Accepted
time: 0ms
memory: 4000kb

input:

3000 1035 10000
891 846 17
473 693 1672
1003 1180 6297
740 2824 8840
228 1318 6677
2346 1405 4113
1046 605 5356
1364 1417 6647
1095 1900 72
2771 9 3018
2825 1016 6209
2133 212 14
2330 2762 1921
2649 2622 9177
2246 1822 5399
2745 2769 5767
1355 2032 6060
2141 2893 6091
174 2306 7016
2736 1469 7939
28...

output:

52655

result:

ok single line: '52655'

Subtask #6:

score: 23
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #138:

score: 23
Accepted
time: 20ms
memory: 9188kb

input:

80000 66844 100
44177 53970 3
9014 59164 1
18681 64098 9
74175 55791 1
22854 38105 10
73740 15631 7
28291 19237 9930
28291 23646 9007
50590 37678 7
74017 51051 7
15080 74829 8
52865 40238 3
64458 41316 5
5426 73753 3
45733 9308 7
23497 9190 6
4622 76092 8
44853 23635 3
2842 55284 5
28291 5903 9707
6...

output:

20000

result:

ok single line: '20000'

Test #139:

score: 23
Accepted
time: 23ms
memory: 11032kb

input:

100000 83613 100
10647 21759 7
17344 43667 6
1793 52207 7
47601 25132 8
45571 61405 2
73183 39360 9
34273 74888 7
44234 21961 6
38977 81279 5
45447 49920 9
81231 46302 4
88357 30116 9486
23273 2334 4
81815 81262 7
88357 44030 9683
81432 92829 9
62554 22228 1
27054 17648 3
88357 83031 9745
29497 5440...

output:

20000

result:

ok single line: '20000'

Test #140:

score: 23
Accepted
time: 20ms
memory: 9456kb

input:

80000 68394 1000
14707 77979 10
30192 62805 10
23667 15854 5000
39450 72073 9
37675 59355 10
13408 42864 5
714 78341 4
55201 60327 1
79438 63265 2
33947 63669 10
70791 79754 2
28170 54447 5000
29267 20600 4
55786 21909 10
61994 39793 10
8492 41656 9
37730 6356 1
70273 10544 2
23667 36159 5000
28170 ...

output:

11000

result:

ok single line: '11000'

Test #141:

score: 23
Accepted
time: 22ms
memory: 11228kb

input:

100000 85415 1000
52408 73740 9
1857 21599 5000
29087 81798 3
1857 89125 5000
81485 31437 2
49676 69231 4
30307 42840 7
73703 5793 5
23114 87065 8
69184 27519 5000
34392 72973 7
27328 78209 3
66879 43807 7
4315 96239 1
90120 43725 10
17633 47286 4
46167 29120 6
58548 83838 1
16381 48438 5
1857 46254...

output:

11000

result:

ok single line: '11000'

Test #142:

score: 23
Accepted
time: 20ms
memory: 9732kb

input:

80000 69810 1000
18113 50530 7
11873 21179 5100
47611 50358 5000
47611 66760 5000
78701 56600 1
57270 38748 1
16826 20360 6
75344 74444 5
3941 1142 3
11873 67979 5100
68275 18022 2
47611 27792 5000
992 74251 8
54171 3324 8
65639 49152 10
47611 69357 5000
10311 71514 1
62162 52380 10
5612 6348 3
1187...

output:

12000

result:

ok single line: '12000'

Test #143:

score: 23
Accepted
time: 31ms
memory: 11144kb

input:

100000 87151 1000
48067 5374 6
48328 21379 2
15290 82785 3
58895 13180 5000
43698 19275 3
46132 42368 5100
46132 38737 5100
55618 50716 7
70303 23569 5000
60845 75225 4
80916 30935 8
46132 63742 5100
19129 82211 10
93638 19310 3
58895 64378 5000
83891 98650 8
88751 38166 7
37349 90826 4
93944 46456 ...

output:

12000

result:

ok single line: '12000'

Test #144:

score: 23
Accepted
time: 32ms
memory: 11384kb

input:

91397 91396 8516
73048 52031 1643
68475 47915 6828
56914 75681 3661
88112 7022 7235
1981 10880 9134
16749 8438 6048
89681 86658 1211
43862 45149 6164
78945 4848 2773
89104 14482 6077
70239 87740 7486
27278 24426 2920
23006 35198 8560
58196 62005 2218
16438 59222 1810
74291 2956 5822
73309 67657 2000...

output:

7910928

result:

ok single line: '7910928'

Test #145:

score: 23
Accepted
time: 36ms
memory: 11236kb

input:

90192 90191 7176
40803 86776 4484
18312 49155 2883
26121 10365 570
53992 87239 3663
26731 89837 274
14104 73727 7350
16058 24043 8466
70257 85820 2513
54371 86594 8130
8930 26030 110
19812 7456 2849
58998 44001 9027
50138 66903 4867
85481 41915 1223
45918 32426 6536
30733 71359 1240
22954 8483 8438
...

output:

8593532

result:

ok single line: '8593532'

Test #146:

score: 23
Accepted
time: 39ms
memory: 14124kb

input:

91090 91089 694
58846 80699 3770
39985 16849 4522
41015 67223 4617
66202 79949 2293
67799 6672 5080
58515 66220 4680
6416 84511 6702
35584 49004 1809
34214 16486 1374
23030 69667 7386
61280 47227 7055
66031 47280 9354
27838 10393 1317
80665 20907 6466
15922 55681 9342
48820 42050 2978
61996 64081 87...

output:

456911072

result:

ok single line: '456911072'

Test #147:

score: 23
Accepted
time: 31ms
memory: 15372kb

input:

98254 98253 3764
62792 6559 4370
65879 87988 8354
76167 69625 7673
40880 8505 1245
13609 48916 7879
89981 79683 8598
51710 89239 510
54642 21429 3198
3194 72907 7560
42872 42834 8956
94 30157 2664
84354 60258 7568
60808 72979 6643
22638 33878 5967
70683 33388 2069
63316 1767 5547
71643 1933 5574
409...

output:

490127917

result:

ok single line: '490127917'

Test #148:

score: 23
Accepted
time: 36ms
memory: 11368kb

input:

91366 91365 6558
1377 45653 7113
69528 34867 7796
53102 3053 6983
12192 89860 185
35532 60873 7638
54339 87618 1777
45083 36694 2896
88151 33261 921
45374 30610 510
21798 2713 1324
13816 64541 3697
9062 22961 6944
64400 8173 2948
81839 72271 8368
64523 8665 2367
13043 23201 9560
47066 16133 3426
879...

output:

8472940

result:

ok single line: '8472940'

Test #149:

score: 23
Accepted
time: 38ms
memory: 11560kb

input:

93379 93378 8587
51603 30108 6808
4423 66234 1883
59627 35222 3808
68859 49397 7998
43037 37696 1841
85225 28237 3512
72263 38645 3414
19365 53149 7019
13037 73907 4471
10139 36901 663
54700 33637 3416
38623 35426 7405
37386 62999 4322
49085 3789 727
42669 92387 9653
40350 29707 7720
9774 79240 7223...

output:

8594611

result:

ok single line: '8594611'

Test #150:

score: 23
Accepted
time: 12ms
memory: 8344kb

input:

100000 18994 1
36981 86741 5
6317 37800 1
9499 10009 5
92020 28033 3
97250 62833 4
83074 77633 4
33677 69965 1
68239 4956 5
40731 9346 4
73226 15820 1
40043 6291 2
2240 27763 3
21949 78622 3
83897 97543 4
13403 44741 1
65376 97829 4
7215 38695 4
27468 70913 5
64214 11139 1
20627 1064 3
65678 36224 5...

output:

46

result:

ok single line: '46'

Test #151:

score: 23
Accepted
time: 19ms
memory: 9260kb

input:

100000 39482 1
51000 78111 2
10975 76638 1
20007 55922 3
8617 62927 3
34324 35240 3
70962 86440 2
69701 24472 5
67921 80333 5
91284 95509 4
58936 57569 1
23126 74638 1
69138 68113 2
34585 19075 5
75220 6715 4
64544 32134 2
82035 54348 4
46078 7918 3
33723 21903 5
21865 35593 1
6245 89933 1
46212 192...

output:

64

result:

ok single line: '64'

Test #152:

score: 23
Accepted
time: 16ms
memory: 9948kb

input:

100000 54143 128
24294 30228 10
41619 70970 2
48950 47444 6
41269 88167 4
60292 51618 4
19579 88222 5
65 90784 9
61325 21781 9
96518 20418 5
73027 80409 9
69642 10180 9
70950 2380 10
7850 11574 3
39037 80861 3
47379 83557 10
9623 46311 5
8761 82155 8
4431 62929 9
87409 79000 3
19851 53846 7
32998 94...

output:

332

result:

ok single line: '332'

Test #153:

score: 23
Accepted
time: 16ms
memory: 9232kb

input:

100000 31907 55
87844 9201 1
94862 77405 10
27611 2379 5
75795 19021 3
64704 2688 10
31790 70169 5
22076 63403 6
38345 75112 6
28002 989 9
62374 42867 10
31780 43454 6
52548 98297 7
63022 95133 2
61084 88804 2
1800 43923 9
73638 20056 5
8418 56739 10
6292 14852 6
80971 4618 4
56576 98761 7
7845 2472...

output:

158

result:

ok single line: '158'

Test #154:

score: 23
Accepted
time: 32ms
memory: 11972kb

input:

100000 99997 10000
48856 7585 5
63693 95419 5
38436 72585 9
47932 12383 4
69092 7135 5
57703 13585 4
24542 24621 5
76626 66962 1
81519 81422 3
58021 80501 7
27669 75582 8
45793 72590 7
77855 98022 1
32634 36501 2
78878 85040 1
10414 58132 7
18003 67893 1
66489 43034 6
25310 39033 7
9816 56540 6
2620...

output:

23472

result:

ok single line: '23472'

Test #155:

score: 23
Accepted
time: 35ms
memory: 12048kb

input:

100000 99997 10000
28044 84449 2
15496 94114 10
96100 93596 4
94628 79324 7
80729 70681 7
38466 45625 10
80263 99611 5
73574 78006 2
45530 32181 3
3741 86492 4
57125 47395 3
37424 13379 8
28450 76683 1
96161 46599 9
19432 14668 6
4744 93826 1
29997 58059 6
35483 13515 6
16245 40818 2
36955 1760 5
61...

output:

23423

result:

ok single line: '23423'

Test #156:

score: 23
Accepted
time: 34ms
memory: 11392kb

input:

100000 92108 1000
75927 62125 998
76200 53468 115
88418 19026 149
31332 27327 969
81430 73252 409
57854 19574 197
25379 26907 512
22416 10298 669
90375 77887 336
4741 38870 219
96723 40701 726
82565 88264 680
32163 25477 497
57391 22763 861
92378 94839 447
25924 49188 107
1489 36740 28
44424 28290 2...

output:

15881

result:

ok single line: '15881'

Test #157:

score: 23
Accepted
time: 28ms
memory: 10832kb

input:

100000 79093 1000
29390 16555 497
69164 92809 261
84630 4421 922
57408 21125 194
47666 33676 78
71279 62960 773
13839 72714 749
44214 48794 593
93607 25598 537
38509 24296 394
28786 44789 981
1227 91591 385
17977 5033 651
70567 24710 45
53932 60199 648
55555 70994 285
58741 10656 886
58377 36247 337...

output:

11525

result:

ok single line: '11525'

Test #158:

score: 23
Accepted
time: 3ms
memory: 7488kb

input:

100000 3226 5251
4097 27666 9618
96571 40131 8935
96564 86600 8582
49080 73534 9640
34737 12794 9147
47707 49481 9771
43030 96418 9890
9022 21933 9692
62700 84329 8192
12931 89550 8333
94761 7843 9103
13622 20268 9110
20981 65475 8172
64732 68844 8167
35021 32294 9439
68571 9023 8908
30407 55528 970...

output:

44805

result:

ok single line: '44805'

Test #159:

score: 23
Accepted
time: 31ms
memory: 10912kb

input:

100000 81945 4808
9951 32132 8378
59167 90896 8743
4177 79559 8316
96505 22401 9137
90490 87982 9477
12255 54487 8277
10714 49797 9970
59612 26618 9176
80006 93058 8633
30705 87829 9944
1444 36141 9153
28330 6577 8755
6784 73155 9962
93335 42881 8519
33554 51280 9903
10079 59009 8238
77021 61892 841...

output:

219778

result:

ok single line: '219778'

Test #160:

score: 23
Accepted
time: 10ms
memory: 9120kb

input:

100000 33333 5168
52051 57250 10000
40322 23453 1
66012 78275 10000
98001 99973 10000
59725 86207 10000
19410 88660 1
31908 78222 10000
93311 18913 1
99239 17423 1
74309 45551 10000
33821 88441 10000
63476 86481 1
36912 14765 1
15471 66773 10000
79365 40606 10000
3928 79151 10000
25067 60736 1
41574...

output:

75169

result:

ok single line: '75169'

Test #161:

score: 23
Accepted
time: 14ms
memory: 9168kb

input:

100000 33333 2188
68273 86981 1
81760 18850 1
94829 34884 1
91892 23308 10000
91354 21577 10000
57083 66578 10000
16699 86267 10000
19709 3986 10000
13903 45461 10000
95294 70357 1
19385 4272 1
59331 79380 10000
76444 9072 10000
7533 96016 1
73694 39019 1
39511 64120 1
99403 7761 10000
67142 55117 1...

output:

64376

result:

ok single line: '64376'

Test #162:

score: 23
Accepted
time: 25ms
memory: 10620kb

input:

100000 72790 169
52644 93224 3002
84794 93651 3001
84947 60083 3001
22047 19892 3002
33865 26204 3000
4740 40779 3000
19215 97561 3002
31465 73467 3000
4190 97767 3000
78694 39535 3000
94747 76242 3000
44866 42017 3001
48268 24635 3002
87256 82647 3001
58355 60519 3000
23135 73052 3002
20710 9223 30...

output:

57186

result:

ok single line: '57186'

Test #163:

score: 23
Accepted
time: 4ms
memory: 7768kb

input:

100000 11607 1173
89391 22116 3000
64461 19175 3001
46340 12814 3002
57227 76149 3001
92432 10552 3002
87799 23511 3002
78176 50816 3000
18809 62231 3000
18472 29901 3000
25257 28448 3000
6824 76545 3002
26967 10375 3001
91310 27039 3001
97283 67519 3000
21895 45254 3000
48600 84017 3000
35437 40657...

output:

16179

result:

ok single line: '16179'

Test #164:

score: 23
Accepted
time: 13ms
memory: 9380kb

input:

100000 33333 1089
17357 76503 3000
79599 60921 3000
20793 69168 3000
25817 14784 3000
50492 34296 3000
17895 68961 3000
57836 99260 3000
53887 58989 3000
41119 81397 3000
79626 6025 3000
73634 30543 3000
26065 61302 3000
78260 73507 3000
21982 57662 3000
82969 81909 3000
94267 181 3000
66406 47186 3...

output:

26178

result:

ok single line: '26178'

Test #165:

score: 23
Accepted
time: 17ms
memory: 9248kb

input:

100000 33333 3190
22592 82900 3000
76573 71085 3000
84982 59818 3000
7423 82540 3000
68328 59657 3000
84340 24635 3000
7178 19433 3000
36495 54435 3000
46270 18056 3000
90050 31117 3000
5001 81206 3000
43154 84927 3000
44187 86862 3000
19513 69756 3000
51032 4083 3000
27696 16149 3000
33301 21166 30...

output:

30380

result:

ok single line: '30380'

Test #166:

score: 23
Accepted
time: 2ms
memory: 7200kb

input:

100000 289 10000
99982 26762 3000
91676 68555 3000
52493 1438 3000
3897 30786 3000
49736 78758 3000
14931 68087 3000
31587 61323 3000
32077 39273 3000
51411 92296 3000
83731 24416 3000
688 46207 3000
88838 59525 3000
93566 69321 3000
49574 98720 3000
50528 70528 3000
64392 96112 3000
58077 9018 3000...

output:

26000

result:

ok single line: '26000'

Test #167:

score: 23
Accepted
time: 32ms
memory: 11404kb

input:

100000 99057 1000
45393 56258 288
7962 48263 811
16399 10443 844
72370 75498 725
82953 57313 796
3977 94063 134
97775 57228 556
24158 79601 267
83170 95322 324
6756 31621 288
11291 43720 62
50867 71472 18
64580 24891 258
23714 93023 830
35748 87274 649
74804 47175 247
74224 70695 505
48469 24071 499...

output:

35228

result:

ok single line: '35228'

Test #168:

score: 23
Accepted
time: 19ms
memory: 11380kb

input:

100000 98926 1000
31045 68930 465
81429 75095 530
60683 73219 730
25362 98793 520
52451 70871 871
91883 80163 41
77429 28438 399
9107 82768 480
89253 11293 769
97068 31637 139
34510 45352 844
61520 18619 911
88342 172 581
99164 18095 239
75315 69438 496
47223 98736 4
13192 15730 470
74717 37834 537
...

output:

33791

result:

ok single line: '33791'

Test #169:

score: 23
Accepted
time: 14ms
memory: 9688kb

input:

100000 54094 10000
84987 95194 10000
0 20275 10000
87026 84093 10000
99998 81316 5
10462 21048 8
99996 74881 10000
99994 85508 3
99993 27100 10000
99992 41234 1
99991 21535 8
99990 842 8
99315 85014 8
36226 83148 5
99989 52255 8
99986 96489 9
99985 4191 10000
99984 5957 5
99983 81743 10
99982 62196 ...

output:

40019

result:

ok single line: '40019'

Test #170:

score: 23
Accepted
time: 13ms
memory: 8616kb

input:

100000 36720 10000
0 16164 10000
99999 6441 10000
23462 2702 10000
99998 11534 10000
88660 70754 10000
3946 52206 10000
99996 63780 10000
99993 35072 10000
99992 81608 10000
99991 55067 10000
99990 30722 10000
99989 65115 10000
68191 58609 10
99988 1237 10000
99986 543 10000
99985 16226 10000
99984 ...

output:

40017

result:

ok single line: '40017'

Test #171:

score: 23
Accepted
time: 18ms
memory: 9616kb

input:

100000 54077 10000
0 69227 869
99999 41080 9841
99998 42713 8760
99997 33693 4393
99996 66138 5379
99995 39003 8588
99994 49600 4934
66052 60259 8535
99993 7442 1056
99991 11824 1594
99990 59679 1707
99989 47209 3564
99988 81126 1770
99987 38802 1167
9983 20200 6933
99986 97685 1993
99984 56618 7669...

output:

260671

result:

ok single line: '260671'

Test #172:

score: 23
Accepted
time: 20ms
memory: 10128kb

input:

100000 63734 10000
0 71885 3360
40563 67501 9143
99999 32330 7557
99997 75265 2464
99996 26754 8381
99995 82492 5636
74074 82992 2631
99994 17105 3253
99992 60146 1440
99991 27354 3855
75548 21141 4689
83353 29559 8170
99990 72316 8663
92248 51974 3656
99987 23734 5301
99985 52976 1739
99984 44355 6...

output:

266758

result:

ok single line: '266758'

Test #173:

score: 23
Accepted
time: 25ms
memory: 10692kb

input:

100000 76669 10000
77799 31653 10000
14922 76460 10000
88712 75440 10000
38301 75923 10000
8555 98478 10000
94274 50408 10000
28899 35410 10000
56312 11561 10000
1996 41016 10000
73094 63179 10000
43608 95919 10000
23498 39912 10000
14911 60301 10000
124 70942 10000
65005 75539 10000
39078 73196 100...

output:

40079

result:

ok single line: '40079'

Test #174:

score: 23
Accepted
time: 24ms
memory: 10180kb

input:

100000 60685 10000
95069 33568 10000
8597 42058 10000
48712 80306 10000
11417 2360 10000
34750 52065 10000
57471 19456 10000
88792 89870 10000
77528 58925 10000
68907 68516 10000
71220 89522 10000
98608 63618 10000
97852 26386 10000
40295 73818 10000
42004 86873 10000
66516 84958 10000
57245 74135 1...

output:

40057

result:

ok single line: '40057'

Test #175:

score: 23
Accepted
time: 16ms
memory: 9200kb

input:

100000 39986 10000
5442 84194 4516
13406 57141 6759
33483 61297 8760
17211 2561 7586
50242 72893 928
19295 10865 4406
91974 7239 8135
90767 48670 9058
20950 39234 5336
74287 83743 466
80278 17610 1009
63800 49 2772
66106 13756 5436
1703 21642 6793
43488 44962 5790
55839 81901 1196
1304 25604 5231
82...

output:

73705

result:

ok single line: '73705'

Test #176:

score: 23
Accepted
time: 27ms
memory: 10604kb

input:

100000 74406 10000
62124 99725 7624
85781 67917 7875
75942 50243 2936
24424 45465 1908
16438 35134 1634
17830 22145 3250
26024 47136 5612
98321 79484 243
85286 10606 4046
12515 13448 7164
24681 29267 4719
52598 90196 6112
22678 7454 4829
86469 50507 9633
94287 78261 6103
72530 1882 3414
87848 71014 ...

output:

128116

result:

ok single line: '128116'