QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#129291#3998. The Profiteertraining4usacoAC ✓328ms21304kbC++172.3kb2023-07-22 14:06:052023-07-22 14:06:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-22 14:06:08]
  • 评测
  • 测评结果:AC
  • 用时:328ms
  • 内存:21304kb
  • [2023-07-22 14:06:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int MAXN = 2e5 + 5;

int n, k, e;
int a[MAXN], b[MAXN], val[MAXN];
int ans[MAXN];
int dp[MAXN];
int dp2[MAXN];

void upd(int w, int v) {
    for(int i = k; i >= w; --i) dp[i] = max(dp[i], dp[i - w] + v);
}

void upd2(int w, int v) {
    for(int i = k; i >= w; --i) dp2[i] = max(dp2[i], dp2[i - w] + v);
}

bool check(int l, int r, int ql, int qr) {
    for(int i = 0; i <= k; ++i) dp2[i] = dp[i];
    
    for(int i = l; i <= r; ++i) {
        if(ql <= i && i <= qr) upd2(b[i], val[i]);
        else upd2(a[i], val[i]);
    }
    
    int sum = 0;
    for(int i = 0; i <= k; ++i) sum += dp2[i];
    return sum <= e * k;
}

void magic(int l, int r, int ql, int qr) {
    if(l > r || ql > qr) return;
    
    if(ql == qr) {
        for(int i = l; i <= r; ++i) ans[i] = ql;
        return;
    }
    
    vector<int> cur(k + 1);
    for(int i = 0; i <= k; ++i) cur[i] = dp[i];
    
    int mid = (l + r) / 2;
    for(int i = l; i < mid; ++i) upd(a[i], val[i]);
    for(int i = mid; i <= min(ql - 1, r); ++i) upd(b[i], val[i]);
    
    int nl = max(mid, ql), nr = qr;
    while(nl <= nr) {
        int nmid = (nl + nr) / 2;
        if(check(nl, nr, mid, nmid)) {
            for(int i = nmid; i <= nr; ++i) upd(a[i], val[i]);
            ans[mid] = nmid; nr = nmid - 1;
        }
        else {
            for(int i = nl; i <= nmid; ++i) upd(b[i], val[i]);
            nl = nmid + 1;
        }
    }
    
    for(int i = 0; i <= k; ++i) dp[i] = cur[i];
    for(int i = mid; i <= min(r, ql - 1); ++i) upd(b[i], val[i]);
    for(int i = ans[mid] + 1; i <= qr; ++i) upd(a[i], val[i]);
    
    magic(l, mid - 1, ql, ans[mid]);
    for(int i = 0; i <= k; ++i) dp[i] = cur[i];
    for(int i = l; i <= mid; ++i) upd(a[i], val[i]);
    for(int i = max(r + 1, ql); i < ans[mid]; ++i) upd(b[i], val[i]);
    
    magic(mid + 1, r, ans[mid], qr);
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    
    cin >> n >> k >> e;
    for(int i = 1; i <= n; ++i) cin >> val[i] >> a[i] >> b[i];
    
    for(int i = 1; i <= n; ++i) ans[i] = n + 1;
    magic(1, n, 1, n + 1);
    
    int sum = 0;
    for(int i = 1; i <= n; ++i) sum += (n - ans[i] + 1);
    cout << sum << endl;
}

詳細信息

Test #1:

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

input:

4 5 3
3 2 4
1 2 3
2 1 2
3 1 3

output:

1

result:

ok single line: '1'

Test #2:

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

input:

4 5 4
3 2 4
1 2 3
2 1 2
3 1 3

output:

3

result:

ok single line: '3'

Test #3:

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

input:

4 5 5
3 2 4
1 2 3
2 1 2
3 1 3

output:

7

result:

ok single line: '7'

Test #4:

score: 0
Accepted
time: 310ms
memory: 10052kb

input:

200000 50 23333
2620 5 21
8192 17 34
6713 38 46
6687 13 42
390 9 13
4192 7 37
7898 17 21
1471 16 45
3579 22 40
9628 8 23
7164 28 45
3669 14 31
5549 29 35
4670 30 39
5811 15 20
4162 18 29
7590 29 41
7786 23 35
383 9 40
5576 39 46
5586 4 9
1110 14 33
8568 4 6
8548 39 42
9133 10 42
6679 22 39
8353 33 3...

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 300ms
memory: 11152kb

input:

200000 50 233332
8019 18 20
3111 27 40
2015 16 47
6491 17 18
1224 30 38
428 23 34
7521 4 41
7252 6 33
4121 32 45
4230 18 35
1605 21 42
9489 17 25
3704 35 45
6202 8 22
6493 1 5
3041 14 46
4509 23 43
9646 11 48
5294 19 27
3562 19 40
9408 30 47
1751 21 29
4053 4 27
5596 32 49
8609 13 29
1686 4 31
3588 ...

output:

17523021

result:

ok single line: '17523021'

Test #6:

score: 0
Accepted
time: 290ms
memory: 11096kb

input:

200000 50 2333331
7420 30 44
8652 22 28
5418 8 21
9825 3 8
4257 21 40
9962 6 16
3370 18 41
2192 37 41
231 8 18
7764 3 41
3455 9 18
1159 8 46
9775 9 42
4400 21 43
4593 10 22
712 7 22
2067 21 27
9618 9 35
8008 13 38
114 4 31
4503 39 49
4661 14 41
4837 15 35
1371 12 16
9568 21 48
8934 16 34
870 4 35
83...

output:

20000100000

result:

ok single line: '20000100000'

Test #7:

score: 0
Accepted
time: 328ms
memory: 11672kb

input:

200000 50 253330
4837 37 46
2436 11 48
2043 24 50
3544 27 40
1499 21 43
9009 36 46
9172 11 17
585 29 44
6379 4 28
6630 25 37
9230 24 35
5736 23 50
4324 34 50
4624 23 47
9933 3 12
577 12 18
4411 24 32
8750 42 48
4808 21 34
3904 7 17
5979 41 48
2838 29 40
8682 25 46
4026 11 19
8371 8 42
4550 6 24
1546...

output:

2513593675

result:

ok single line: '2513593675'

Test #8:

score: 0
Accepted
time: 307ms
memory: 10360kb

input:

200000 50 193334
8521 14 21
3902 5 6
2949 4 41
1034 10 36
6156 16 36
9432 35 37
3752 25 37
9668 5 9
3194 43 45
9849 1 26
1582 6 10
9920 20 50
994 34 50
9510 12 38
4513 18 31
6294 3 48
4949 9 18
2348 10 49
5492 19 46
2265 3 37
67 20 40
8752 1 5
4610 27 41
7344 27 39
7767 16 29
921 7 16
1853 23 44
936...

output:

1432887

result:

ok single line: '1432887'

Test #9:

score: 0
Accepted
time: 181ms
memory: 10420kb

input:

100000 100 304560
2347 27 64
3715 15 62
6005 16 86
9856 21 55
1347 5 89
9403 25 33
3889 36 74
554 18 95
5218 27 72
3282 2 68
4955 48 83
3478 7 36
3917 34 99
2117 24 41
9764 35 52
7991 81 94
8026 55 69
7755 27 44
3568 18 50
1968 36 57
7992 63 67
7760 4 55
6938 4 53
722 89 99
1111 47 66
5995 71 80
510...

output:

6114559

result:

ok single line: '6114559'

Test #10:

score: 0
Accepted
time: 183ms
memory: 9708kb

input:

100000 100 404561
3114 87 96
4983 68 99
4734 9 65
3721 49 79
7965 40 74
4463 33 81
731 7 61
9048 36 50
6891 40 68
4236 2 43
5436 6 45
1643 64 85
6889 5 95
5673 21 42
2119 57 70
2940 14 98
5620 59 67
8567 76 90
7543 81 99
5576 4 51
7281 4 100
2485 55 75
9357 6 45
4345 33 62
2261 7 26
2371 4 44
9758 5...

output:

29508633

result:

ok single line: '29508633'

Test #11:

score: 0
Accepted
time: 188ms
memory: 9936kb

input:

100000 100 454562
4294 4 37
7975 12 19
4648 1 83
674 41 84
8184 33 57
9088 56 79
2734 56 60
411 11 52
267 20 41
3503 75 86
6921 24 90
1255 49 90
1841 25 27
7767 86 97
9921 25 26
3063 23 44
9237 10 32
4991 7 87
969 36 100
5989 21 87
1420 45 73
780 7 26
6408 85 90
33 31 41
9767 36 89
7666 16 35
3725 1...

output:

160913569

result:

ok single line: '160913569'

Test #12:

score: 0
Accepted
time: 129ms
memory: 10172kb

input:

50000 200 604563
7628 31 102
3694 47 127
4931 101 187
332 7 146
800 131 143
6750 50 136
3718 88 108
5113 36 188
6565 16 49
7739 66 159
215 97 125
1184 90 150
6960 41 173
2281 18 66
3221 144 155
3431 12 162
4191 59 164
8530 28 30
2720 103 196
1176 171 194
2328 124 200
8209 62 114
2606 6 168
1201 120 ...

output:

97043020

result:

ok single line: '97043020'

Test #13:

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

input:

50000 200 804564
2147 132 170
2582 142 185
2492 29 44
4085 50 81
2749 40 115
7068 3 49
5096 72 127
2097 71 122
6697 130 145
6755 141 163
6197 66 130
3397 136 167
7546 71 156
7798 153 169
655 91 94
9498 62 117
7881 71 112
582 67 100
2382 6 189
7366 101 116
2254 56 138
4321 68 125
1601 44 54
2186 65 1...

output:

566251550

result:

ok single line: '566251550'

Test #14:

score: 0
Accepted
time: 147ms
memory: 9656kb

input:

50000 200 824565
2301 142 166
3523 60 153
3438 18 182
4052 42 116
6084 106 166
5687 45 55
2362 34 57
891 171 177
4412 18 49
3142 99 186
9489 86 103
7153 32 90
8357 35 115
6666 161 181
9346 160 196
6328 60 119
3756 16 135
990 130 150
4038 113 128
3608 69 127
8803 119 193
7508 100 141
2918 96 179
5466...

output:

718514472

result:

ok single line: '718514472'

Test #15:

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

input:

50000 200 844566
3943 49 169
1142 177 181
5370 77 91
9254 48 141
1986 87 196
8256 21 188
4440 116 174
6575 5 126
6139 8 67
5192 44 66
3795 51 60
2574 93 139
9861 46 164
3735 46 149
4388 19 46
3578 110 138
6011 25 99
9446 145 189
9215 22 156
9708 119 128
4207 28 172
1229 19 121
4672 161 174
938 35 60...

output:

832753831

result:

ok single line: '832753831'

Test #16:

score: 0
Accepted
time: 122ms
memory: 9756kb

input:

50000 200 864567
1496 192 200
501 22 137
8461 144 151
6841 56 92
4249 5 170
8990 100 155
8686 54 66
3745 144 175
406 127 179
8669 94 108
6146 141 187
1715 178 188
9270 20 160
1541 12 19
9499 66 132
2513 124 152
6228 83 126
8232 106 133
9816 101 197
7403 28 98
4128 14 113
2935 162 190
9541 78 166
773...

output:

1250025000

result:

ok single line: '1250025000'

Test #17:

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

input:

20000 500 604507
8220 251 441
473 267 330
7866 43 172
1675 178 390
7373 216 466
5691 122 274
4101 219 461
7195 406 475
3120 229 462
9594 164 276
8539 4 337
4490 98 498
6378 297 375
2771 40 144
5832 127 372
7877 6 438
9080 140 247
3343 56 354
4402 329 451
7275 56 90
8068 32 47
1412 143 373
9605 17 41...

output:

22551597

result:

ok single line: '22551597'

Test #18:

score: 0
Accepted
time: 99ms
memory: 9728kb

input:

20000 500 704517
6908 150 406
9324 73 113
9557 128 342
3522 265 344
5140 74 283
6988 397 456
8814 436 439
8944 74 400
9177 158 459
6200 105 230
2367 4 247
5138 402 427
9506 181 272
3341 94 396
8436 34 396
3890 195 466
2215 364 372
8343 159 489
7693 57 82
1961 43 74
3854 205 350
5171 38 87
9512 377 4...

output:

46171637

result:

ok single line: '46171637'

Test #19:

score: 0
Accepted
time: 99ms
memory: 9844kb

input:

20000 500 804527
694 70 142
6628 18 245
8865 27 483
472 22 297
5019 332 444
618 411 474
8356 336 483
2233 353 367
3244 193 322
4513 28 455
4447 52 243
7911 8 270
3402 49 469
6244 427 449
7769 27 359
8126 33 108
7584 314 358
6188 115 337
2092 38 154
6307 46 389
7366 34 362
4285 150 393
9307 399 419
6...

output:

90970591

result:

ok single line: '90970591'

Test #20:

score: 0
Accepted
time: 96ms
memory: 9756kb

input:

10000 1000 704537
6257 67 731
8667 640 807
7190 16 344
8470 336 963
5114 32 272
4196 825 946
8056 363 991
7445 616 873
242 237 944
2998 694 786
1256 105 229
3271 538 719
7616 451 687
8292 65 854
6622 407 883
4558 643 805
9402 240 572
1664 182 253
6327 702 851
6549 232 479
3798 22 490
8720 597 963
15...

output:

44558728

result:

ok single line: '44558728'

Test #21:

score: 0
Accepted
time: 79ms
memory: 9920kb

input:

5000 2000 404547
1199 130 149
2031 232 1571
8922 942 1218
7294 143 166
7867 364 666
5214 609 1185
785 618 1453
4296 1165 1731
7467 939 1711
4932 32 336
1804 1377 1750
6492 279 846
3487 361 516
7077 1668 1909
2759 781 1319
1519 574 1831
5072 389 971
7269 521 1155
2308 707 713
1947 288 930
2934 443 76...

output:

3355833

result:

ok single line: '3355833'

Test #22:

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

input:

3000 3000 204557
3644 409 2773
9860 1718 1833
6980 849 1708
5059 744 878
5394 1473 2309
6100 1424 2358
4621 338 2392
8682 781 1500
2734 822 1792
1935 562 1215
6772 454 750
8506 453 1765
3681 1742 2506
6915 387 1496
3963 1943 2004
6263 1859 2591
3124 334 897
3631 352 1380
1132 1075 1753
7719 1832 196...

output:

404256

result:

ok single line: '404256'

Test #23:

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

input:

3000 3000 254557
5040 794 2655
8982 113 2414
2507 796 1594
1127 224 1427
694 655 1184
3136 1607 2269
606 750 1453
7027 696 1263
5853 523 2414
4896 129 2589
7544 878 2295
689 368 1422
5719 1397 1848
3939 835 887
2854 550 738
7426 283 2732
4328 1468 1676
6199 657 1514
8612 1284 1601
6594 288 2356
9930...

output:

626919

result:

ok single line: '626919'

Test #24:

score: 0
Accepted
time: 70ms
memory: 9860kb

input:

3000 3000 304557
9819 663 846
4223 2500 2553
2955 2016 2896
9526 1334 1873
2184 985 1087
1539 1303 2638
6366 2141 2314
8445 329 2572
7882 1503 2075
5998 925 1904
779 1964 2148
2609 774 1142
7463 1613 1986
8926 819 1402
3880 1446 1669
7101 201 1722
8076 273 2570
8653 1484 2658
3424 2201 2591
7281 282...

output:

1789494

result:

ok single line: '1789494'

Test #25:

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

input:

3000 3000 354557
9782 185 1593
3837 2922 2949
8960 518 1539
3903 73 768
3087 2284 2848
4054 239 1071
8856 920 1389
9133 2053 2528
2062 1764 2649
1854 992 2275
6359 205 373
3649 1397 1419
6880 2285 2912
2055 1350 2453
318 1886 1971
4250 829 2565
313 1188 2713
3727 113 2141
3288 627 2569
2197 116 2099...

output:

2198841

result:

ok single line: '2198841'

Test #26:

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

input:

3000 3000 404557
708 802 2784
6640 109 1264
6684 46 1872
2837 1443 2707
587 1190 2330
6780 621 1708
2159 1522 1704
8738 1483 1908
238 137 516
3032 1739 2649
3675 1249 2777
1836 46 1902
1388 1713 2947
5627 476 1478
3073 812 1039
1235 2360 2589
9211 167 2441
8579 1740 2393
1982 461 2914
8369 865 925
8...

output:

3206289

result:

ok single line: '3206289'

Test #27:

score: 0
Accepted
time: 74ms
memory: 9932kb

input:

2000 5000 304567
3784 2499 5000
3491 2864 4941
3594 2101 3768
8110 1158 3663
1039 751 4924
333 80 2728
844 1083 4516
1940 63 3261
4414 1718 2352
4158 1027 3827
7048 1886 3090
7294 2842 3093
9489 1056 4955
5573 3166 4734
737 1959 3819
7890 2266 4309
7453 1680 4291
237 419 486
5602 495 1736
4968 487 4...

output:

1814585

result:

ok single line: '1814585'

Test #28:

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

input:

1000 10000 204577
1152 5103 9381
8782 268 5975
7743 6743 7323
8250 8412 8621
3987 7810 9955
9988 3263 5353
3267 1270 2302
9258 1791 8246
6156 5588 5865
3605 173 2370
6062 4685 6687
2097 6056 7346
7872 1131 1820
9835 5267 8695
6997 3397 9090
6233 6312 6664
361 309 743
3467 5699 8922
7766 670 7035
815...

output:

87842

result:

ok single line: '87842'

Test #29:

score: 0
Accepted
time: 49ms
memory: 11124kb

input:

500 20000 104587
964 4142 16635
6646 6532 10065
7296 7455 19855
4317 10262 10674
737 10824 12615
1947 5010 6953
2191 4137 18435
692 5757 13061
6052 14796 15895
4903 1335 13698
3006 927 7492
8096 952 4912
8212 10091 14249
9475 13819 14844
6903 3421 10365
2033 15662 17575
2061 4732 13496
1339 5005 152...

output:

38003

result:

ok single line: '38003'

Test #30:

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

input:

200 50000 74597
9588 27711 49855
5798 13401 35454
3163 37425 43074
1300 14772 49588
5445 8585 44770
3393 18689 43728
7747 5528 32127
1335 16928 45939
2038 10120 35057
7556 4277 19641
5989 2879 46380
8818 29554 36714
8791 2348 40820
9264 29592 34761
2033 826 29568
2253 40270 48103
6498 3469 22981
103...

output:

4693

result:

ok single line: '4693'

Test #31:

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

input:

100 100000 64067
3830 10209 47413
2236 11577 63433
602 12486 15366
9978 39578 67766
4732 80805 93353
1222 64481 86851
4368 29603 38059
6669 13473 73241
6857 33194 50911
6248 37920 39054
9414 10801 73316
6527 11781 63154
3570 53755 56008
5385 7820 34323
4335 37647 92580
8397 27180 82736
2773 71697 89...

output:

5050

result:

ok single line: '5050'

Test #32:

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

input:

50 200000 2167
5125 2778 70281
7973 49883 131314
6688 60715 63660
1842 64990 87433
2170 44234 140368
7454 5352 106136
740 49479 73311
683 74708 188982
1814 74591 148654
9219 36677 158650
5554 4211 170022
6362 48921 68439
7925 6840 88248
6590 38020 186698
3803 24350 76742
6265 54217 119088
1303 58245...

output:

0

result:

ok single line: '0'

Test #33:

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

input:

50 200000 4167
6609 143489 170762
434 28498 122523
1227 39445 153286
7182 67865 156238
2850 88324 174863
9332 43804 102485
8834 55181 123990
1101 80491 164065
6758 104936 132629
5497 18085 184894
2385 90449 193119
5840 22417 46690
5918 9637 188692
1496 154233 158153
3819 101861 121123
9746 55797 180...

output:

0

result:

ok single line: '0'

Test #34:

score: 0
Accepted
time: 37ms
memory: 18956kb

input:

50 200000 7167
7703 52615 124671
9171 112234 122718
4898 73136 156936
44 17394 39016
2675 15166 116007
3571 26765 197777
4250 118182 187213
2203 102983 191342
7337 92218 110455
8602 87335 154991
8615 57163 114174
1746 23030 163737
3675 13164 87869
5748 12601 113569
7713 9949 20072
5369 99739 161123
...

output:

0

result:

ok single line: '0'

Test #35:

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

input:

50 200000 10167
8075 59281 59771
7041 117846 144814
6023 117104 132757
5542 71215 145103
2826 59190 86575
6164 70537 156429
4401 37851 54386
4588 50954 69363
8340 155681 170235
8904 89500 124427
6087 42177 151934
1285 58299 111323
1944 147771 183280
7506 41632 89665
5947 39825 144201
7518 94117 1937...

output:

21

result:

ok single line: '21'

Test #36:

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

input:

50 200000 14167
8475 123768 166527
850 29097 94804
5234 3747 28169
4356 44647 182942
1534 34124 119082
568 41249 169003
5523 25967 179160
4199 125909 195567
3709 83310 107375
3 88826 154545
9018 120591 150466
5795 2365 79805
4236 114610 142555
1315 36306 192017
9097 139543 181116
4774 46101 62074
44...

output:

4

result:

ok single line: '4'

Test #37:

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

input:

50 200000 24267
860 56050 101280
9482 12523 82739
7002 96274 167332
1735 31033 120671
1444 20893 177228
9069 79034 104342
4663 4108 175891
9156 11549 94621
7680 68395 163471
4626 62487 139183
9789 84524 165403
3513 162012 169007
1202 78679 176824
5813 73637 158062
4403 2046 125475
2770 122228 168401...

output:

62

result:

ok single line: '62'

Test #38:

score: 0
Accepted
time: 49ms
memory: 21304kb

input:

50 200000 34367
541 155629 179137
4059 22479 137541
6141 159107 188389
278 19063 23156
5135 17960 76747
1840 58827 190124
2608 171542 171885
8786 49163 190480
6538 69653 102189
1768 100965 190700
1403 10354 86777
3623 86885 89463
5140 58840 86043
329 56549 57262
5265 103074 120836
8925 2951 162804
4...

output:

330

result:

ok single line: '330'

Test #39:

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

input:

50 200000 44467
223 31016 113891
7147 175538 192343
7660 42812 105830
209 102077 129868
5152 94434 191559
8388 87639 117730
1485 28204 132552
8809 170745 186947
2341 93961 124618
23 39919 45097
3256 52611 124108
8333 143322 151453
6180 123405 124163
53 88094 151622
9742 10524 197180
3380 164772 1675...

output:

1002

result:

ok single line: '1002'

Test #40:

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

input:

50 200000 54567
2608 163298 191748
1336 151724 199218
7583 75268 132388
5708 20567 51030
1886 53039 192285
2434 4767 31740
6958 22347 133016
1841 10426 42371
4880 117264 198594
4871 38818 130913
982 83057 178873
7248 89559 151763
7588 133893 153628
7632 33222 98881
9013 169605 170072
1552 66387 8257...

output:

1275

result:

ok single line: '1275'

Test #41:

score: 0
Accepted
time: 93ms
memory: 20236kb

input:

50 200000 124567
8046 1673 12320
4527 7633 8347
6065 8788 17721
50 14367 16764
1647 6095 15154
7163 3247 10494
1414 2538 13294
4240 10028 18944
8246 9681 11495
589 11293 13298
823 6913 9049
7983 5440 14413
8809 3631 12404
1209 4002 14933
2872 5832 19658
1125 13153 17742
7418 15711 17634
3361 8078 13...

output:

1109

result:

ok single line: '1109'

Test #42:

score: 0
Accepted
time: 106ms
memory: 10344kb

input:

1000 10000 404577
8343 397 497
7095 129 853
4996 483 714
540 4 102
908 617 926
4941 119 137
700 99 134
9050 907 983
7465 41 387
4598 355 797
9844 116 664
2758 37 392
2373 134 220
2582 52 842
1695 142 964
2713 257 673
5383 256 593
5861 379 630
8529 342 440
959 92 197
7169 333 496
1403 30 797
3521 72 ...

output:

33293

result:

ok single line: '33293'

Test #43:

score: 0
Accepted
time: 106ms
memory: 9840kb

input:

3000 3000 354557
667 39 264
3290 162 213
4403 20 82
8045 204 266
2342 18 220
8238 70 120
2250 26 253
141 212 237
5243 26 70
6561 74 159
9703 135 163
6195 69 270
2266 34 73
587 33 231
6431 104 252
5090 171 280
5682 131 134
2588 24 235
4331 100 252
425 66 227
5629 241 291
2241 132 254
9779 56 145
8481...

output:

6561

result:

ok single line: '6561'

Test #44:

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

input:

20000 500 804527
8691 2 48
4859 5 38
4936 2 7
9992 7 23
8808 21 37
3404 22 27
6721 44 47
2131 3 24
6770 34 39
7363 4 32
5975 4 39
6400 3 15
7312 1 48
811 32 40
7166 6 9
1480 5 39
5679 3 40
1423 44 46
6806 34 43
4842 20 47
1077 11 36
5635 36 46
972 3 23
751 11 48
7863 17 34
6453 18 43
469 5 29
7342 1...

output:

798093

result:

ok single line: '798093'

Test #45:

score: 0
Accepted
time: 219ms
memory: 9752kb

input:

100000 100 404561
5263 2 10
8739 6 7
4158 4 9
5983 4 8
4830 4 7
8523 6 8
8669 5 7
143 3 9
4474 1 4
8342 1 5
7599 9 10
7289 7 10
7332 2 3
7176 1 8
6669 5 6
4666 8 9
4037 1 6
952 8 9
1605 1 4
208 1 10
7461 2 9
6393 3 5
3449 1 7
8153 2 4
3293 7 9
4766 1 5
9760 4 6
6528 2 4
9026 8 10
2665 5 7
4063 2 6
5...

output:

259833

result:

ok single line: '259833'

Test #46:

score: 0
Accepted
time: 259ms
memory: 11028kb

input:

200000 50 253330
1631 1 3
5059 2 3
3034 2 3
2357 1 3
5126 1 3
5075 1 3
5402 1 4
2726 3 4
1293 2 4
4754 2 3
4080 3 5
6605 2 4
5720 1 5
8507 2 5
1701 2 5
2164 2 5
7377 3 4
4295 1 2
610 1 4
675 2 5
8173 4 5
928 2 3
5631 3 5
3207 3 5
9824 2 3
7127 3 5
4797 3 5
7650 2 5
3751 1 3
9051 1 5
490 1 4
661 1 2
...

output:

23812305

result:

ok single line: '23812305'

Test #47:

score: 0
Accepted
time: 108ms
memory: 9796kb

input:

3000 3000 1333333
9980 3 5
9918 4 5
9937 2 5
9913 2 5
9916 4 5
9915 3 5
9930 3 4
9918 4 5
9954 1 5
9948 2 4
9930 3 4
9933 4 5
9921 2 4
9941 1 5
9978 2 3
9964 3 4
9936 4 5
9933 1 3
9914 4 5
9910 1 5
9988 1 2
9982 1 3
9907 4 5
9932 3 4
9918 1 2
9910 1 2
9951 1 5
9921 3 5
9989 2 3
9920 1 4
9909 2 4
996...

output:

0

result:

ok single line: '0'

Test #48:

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

input:

3000 3000 2333333
9955 1 2
9910 1 2
9928 1 3
9993 2 4
9969 1 3
9901 3 5
9916 2 3
9920 1 5
9972 1 5
9975 2 3
9992 3 5
9958 2 4
9917 1 3
9977 3 4
9909 1 2
9914 4 5
9959 1 5
9962 3 4
9999 1 4
9960 1 2
9999 2 3
9952 1 2
9972 1 5
9901 4 5
9974 2 3
9914 4 5
9956 1 5
9941 1 2
9916 1 3
9990 2 5
9935 2 3
992...

output:

0

result:

ok single line: '0'

Test #49:

score: 0
Accepted
time: 99ms
memory: 9856kb

input:

3000 3000 233333333
9978 1 3
9962 1 2
9920 2 4
9929 3 4
9925 4 5
9941 3 5
9980 2 4
9909 3 5
9914 1 2
9958 1 5
9974 1 4
9922 2 4
9945 2 3
9960 2 4
9909 1 2
9999 2 4
9949 4 5
9990 1 4
9992 3 5
9987 3 5
9915 3 4
9933 4 5
9963 1 3
9961 4 5
9988 1 3
9956 1 2
9990 1 4
9955 1 2
9976 1 3
9956 1 2
9912 3 5
9...

output:

4501500

result:

ok single line: '4501500'

Test #50:

score: 0
Accepted
time: 96ms
memory: 9812kb

input:

3000 3000 1000000000
9932 1 2
9941 2 5
9986 3 4
9987 4 5
9961 1 4
9992 3 4
9902 2 4
9938 1 2
9951 1 3
9994 2 3
9965 1 3
9950 2 4
9963 3 5
9963 3 5
9963 2 4
9901 2 5
9948 3 4
9953 2 4
9942 2 3
9902 2 3
9902 1 2
9973 2 3
9974 2 3
9931 3 5
9977 3 5
9925 2 4
9912 4 5
9969 2 3
9976 2 5
9907 1 5
9947 4 5
...

output:

4501500

result:

ok single line: '4501500'

Test #51:

score: 0
Accepted
time: 261ms
memory: 10964kb

input:

200000 50 253150
3417 3 5
5703 2 5
1259 2 3
1128 1 2
6393 2 5
6923 2 3
2652 1 3
912 4 5
1512 2 4
3657 2 5
5010 1 2
3115 3 5
9910 3 4
7418 1 5
4118 2 5
8356 2 4
5041 2 5
1980 1 4
8462 3 4
9374 1 4
6072 4 5
9040 1 5
7581 1 2
9486 1 3
505 2 4
6573 1 3
9417 2 4
4210 1 4
1401 4 5
8497 2 4
4144 3 4
4982 1...

output:

12338351

result:

ok single line: '12338351'

Test #52:

score: 0
Accepted
time: 296ms
memory: 10124kb

input:

200000 50 253021
4305 9 12
1502 7 9
379 10 12
7209 4 10
6665 1 10
3190 1 2
303 1 12
8278 1 9
7731 2 10
3271 6 7
5207 7 10
3712 1 5
7176 1 9
1625 9 12
244 3 7
6187 7 11
7212 5 8
5651 6 7
8764 5 11
444 4 5
52 8 9
3902 10 12
9185 7 12
2490 2 6
1216 2 10
2532 1 8
2914 6 11
1448 2 10
7678 5 6
4809 2 9
30...

output:

73081104

result:

ok single line: '73081104'

Test #53:

score: 0
Accepted
time: 289ms
memory: 10716kb

input:

200000 50 250749
4324 5 9
1113 5 7
6156 5 9
954 6 9
7962 4 5
1518 7 9
3843 2 4
2282 1 8
3343 1 6
758 5 7
3300 3 6
8241 3 9
8236 4 9
9044 5 6
7418 5 6
5634 1 9
9846 6 9
2489 3 8
3675 3 8
5248 3 4
2009 5 9
3478 1 6
792 2 3
279 6 9
6283 3 7
4270 2 5
8509 1 2
8458 7 9
8358 3 5
3279 3 9
9328 1 7
3742 1 7...

output:

6735228

result:

ok single line: '6735228'

Test #54:

score: 0
Accepted
time: 267ms
memory: 10680kb

input:

200000 50 251859
1007 3 6
8254 1 4
8065 4 7
9584 3 8
8793 4 7
5657 3 6
1209 5 7
7479 5 7
2182 1 8
6372 2 7
5885 5 7
6969 3 8
6395 3 5
8975 4 6
127 3 7
1845 6 8
265 1 4
2060 2 5
2363 2 4
5574 4 7
3890 2 5
5151 4 8
1261 4 6
6182 2 3
6279 1 5
4822 6 8
3550 5 7
9432 6 8
8389 4 8
8933 6 7
6422 3 7
5143 4...

output:

16528334

result:

ok single line: '16528334'

Test #55:

score: 0
Accepted
time: 299ms
memory: 10568kb

input:

200000 50 254088
2493 1 3
2530 5 12
5646 6 7
5164 2 3
8871 8 12
6936 3 5
110 1 12
1182 7 12
3238 5 6
9852 2 7
6461 1 4
1268 6 9
9363 7 11
1597 2 12
2692 3 11
9933 10 12
7474 6 11
8193 7 8
5103 1 3
8097 6 12
6561 5 6
3015 1 7
9091 3 12
5375 2 8
3501 7 11
71 3 6
1255 5 6
8744 4 7
4072 4 7
7991 7 12
38...

output:

429305999

result:

ok single line: '429305999'

Test #56:

score: 0
Accepted
time: 287ms
memory: 10936kb

input:

200000 50 252485
5725 1 2
2923 6 11
4058 2 3
7486 3 6
4215 1 8
1908 4 9
7256 8 9
3289 1 4
4373 1 5
4727 1 3
1840 2 8
2648 7 10
4468 3 11
8885 3 4
2998 3 8
2410 6 9
2379 2 3
8607 1 10
347 1 2
8432 3 9
1373 1 9
3607 3 11
8147 4 6
3892 4 9
442 8 11
6518 4 10
5672 2 7
6551 1 8
8732 5 9
3300 7 8
7104 2 4...

output:

34346982

result:

ok single line: '34346982'

Test #57:

score: 0
Accepted
time: 311ms
memory: 11400kb

input:

200000 50 251295
1763 3 6
9256 1 4
9920 3 9
7023 6 11
7190 7 9
8721 3 15
1488 6 13
7087 8 9
3359 8 14
8896 6 10
7149 2 10
8756 3 7
1771 6 9
6680 2 13
7108 8 9
905 4 13
5999 2 4
5548 8 14
882 3 8
1972 12 15
1065 10 12
2608 3 10
2838 9 12
5690 13 15
1887 9 14
5826 4 13
9430 5 8
146 3 14
7933 7 8
4417 ...

output:

38310015

result:

ok single line: '38310015'