QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#29389#366. Long Distance CoachETK100 ✓97ms11632kbC++231.9kb2022-04-17 17:20:092024-07-05 05:46:32

Judging History

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

  • [2024-07-05 05:46:32]
  • 评测
  • 测评结果:100
  • 用时:97ms
  • 内存:11632kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-17 17:20:09]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define inf 1e18
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int MAXN=2e5+5;
struct node{
    int D,C;
    bool operator <(const node a)const{return D<a.D;}
}a[MAXN];
int X,N,M,W,T,S[MAXN],f[MAXN],stk[MAXN],top=1;
bool cmp(int a,int b){return a%T<b%T;}
//斜率优化
pii Node(int x){return {-x*W,f[x]-a[x].C};}
long double slope(pii A,pii B){
    return 1.0*(A.se-B.se)/(A.fi-B.fi);
}
bool chk(int a,int b,int c){
    pii A=Node(a),B=Node(b),C=Node(c);
    return slope(A,B)<slope(A,C);
}
int calc(pii A,int x){return A.fi*x+A.se;}
int get(int X){//单调栈上二分
    int L=1,R=top;
    while(L<R){
        int mid=(L+R)>>1;
        if(calc(Node(stk[mid]),X)>calc(Node(stk[mid+1]),X)){
            L=mid+1;
        }else R=mid;
    }
    return calc(Node(stk[L]),X);
}
signed main(){
    X=read(),N=read(),M=read(),W=read(),T=read();
    rep(i,1,N)S[i]=read();
    S[++N]=X;
    rep(i,1,M){
        a[i].D=read(),a[i].C=read();
    }
    sort(S+1,S+N+1,cmp);sort(a+1,a+M+1);
    a[M+1].D=T;
    rep(i,1,M)a[i].C+=a[i-1].C;
    memset(f,0x3f,sizeof(f));f[0]=0;
    int pos=1;
    while(pos<=N&&S[pos]%T<=a[1].D)pos++;
    rep(i,1,M){
        int Min=inf;
        while(pos<=N&&S[pos]%T<a[i+1].D){
            Min=min(Min,S[pos++]/T);
        }
        //留人
        f[i]=f[i-1]+((X-a[i].D)/T+1)*W;
        //cnm,退钱!
        if(Min!=inf){
            f[i]=min(f[i],get(Min)+Min*W*i+a[i].C);
        }
        while(top>1&&chk(stk[top-1],stk[top],i))--top;
        stk[++top]=i;
    }
    printf("%lld\n",f[M]+(X/T+1)*W);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 16
Accepted

Test #1:

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

input:

999999999999 1 1 1000000 4
1
2 3

output:

499999999999000003

result:

ok single line: '499999999999000003'

Test #2:

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

input:

5 1 1 15 4
2
3 4

output:

45

result:

ok single line: '45'

Test #3:

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

input:

5 1 1 15 4
3
2 13

output:

43

result:

ok single line: '43'

Test #4:

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

input:

5 1 1 15 4
3
2 19

output:

45

result:

ok single line: '45'

Test #5:

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

input:

142 4 7 10 13
67
44
86
141
3 1000000000
6 1000000000
9 1000000000
1 60
4 81
7 48
10 14

output:

878

result:

ok single line: '878'

Test #6:

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

input:

142 3 8 10 13
68
46
37
4 1000000000
8 1000000000
1 61
2 59
5 79
6 79
9 20
10 155

output:

982

result:

ok single line: '982'

Test #7:

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

input:

150 8 8 10 18
5
88
75
87
83
14
109
112
17 30
7 70
2 24
10 25
12 34
9 92
8 30
13 18

output:

463

result:

ok single line: '463'

Test #8:

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

input:

10000000000 8 8 6 18
9547257284
4226673527
9454195771
9513946487
7287482436
6692534804
3951479147
8774939403
12 415893810
4 735304001
13 184845346
14 354080601
15 455062532
16 886416267
3 985580216
1 97417991

output:

18443869092

result:

ok single line: '18443869092'

Test #9:

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

input:

200 4 8 5 14
136
180
37
58
13 39
8 100
3 33
11 32
6 62
5 1
7 98
1 32

output:

601

result:

ok single line: '601'

Test #10:

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

input:

200 8 8 5 18
73
40
168
152
10
12
122
178
3 46
5 30
7 18
9 40
11 24
13 12
15 17
17 9

output:

370

result:

ok single line: '370'

Test #11:

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

input:

99999999999 7 7 3 16
75171012465
68638795379
63875989701
83563043959
64144786889
89597405323
74981605181
2 105022615
4 341401908
6 209850215
8 507409549
10 849182839
12 760157370
14 257217651

output:

116398917650

result:

ok single line: '116398917650'

Test #12:

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

input:

150 8 8 10 18
146
49
17
101
117
134
131
33
1 1
3 1
7 5215
12 2283658
4 69
14 23058601
16 170888234
10 148221

output:

751

result:

ok single line: '751'

Test #13:

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

input:

8001 7 8 6 17
3613
4410
5581
2885
1918
934
6395
10 131687242
13 284628020
2 541922
15 554928957
4 4115226
6 17341529
1 16935
8 52922149

output:

25422

result:

ok single line: '25422'

Test #14:

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

input:

250 8 8 10 18
238
189
86
221
120
173
53
205
6 300728
13 24836451
8 2800753
15 946925513
2 293
10 17341529
1 251803956
3 16935

output:

1260

result:

ok single line: '1260'

Test #15:

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

input:

1234567 8 8 1000000 18
2
22
42
62
82
102
122
142
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1

output:

137203000007

result:

ok single line: '137203000007'

Test #16:

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

input:

1234567 8 8 999 18
449660
490828
187404
376334
697798
1177644
1056704
312928
3 996683357
5 928740029
7 950657139
9 904761397
11 923725553
13 962648669
15 971692610
17 965766352

output:

616666716

result:

ok single line: '616666716'

Test #17:

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

input:

200 8 8 12 18
131
170
55
60
47
28
158
192
13 40
16 87
17 69
4 55
7 99
9 975663280
15 17
3 912112332

output:

1159

result:

ok single line: '1159'

Test #18:

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

input:

600 8 8 63 18
340
333
326
328
331
339
332
337
5 17
3 12
11 26
14 18
12 943485371
17 25
10 954990891
1 48

output:

15089

result:

ok single line: '15089'

Test #19:

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

input:

300 8 8 11 18
135
256
73
167
222
223
206
46
3 22
11 9
15 54
17 47
16 10
13 34
14 54
2 55

output:

1373

result:

ok single line: '1373'

Test #20:

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

input:

300 8 8 11 18
109
113
205
26
208
290
168
189
11 6
13 43
15 21
3 60
17 11
14 69
16 50
4 61

output:

1392

result:

ok single line: '1392'

Test #21:

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

input:

300 8 8 11 18
205
201
265
59
261
268
251
186
14 38
2 17
10 60
1 76
11 6
8 11
15 44
4 42

output:

1285

result:

ok single line: '1285'

Test #22:

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

input:

1000000000000 2 8 1 12
993108218019
991995612814
9 240664344
11 304345424
2 53636225
6 980780804
1 630139807
7 493422072
5 645833104
8 715127198

output:

748927437875

result:

ok single line: '748927437875'

Subtask #2:

score: 30
Accepted

Dependency #1:

100%
Accepted

Test #23:

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

input:

40404 100 100 100 202
11311
6858
1342
33586
9137
32534
4418
17596
219
36087
27700
32608
9038
37603
9907
4425
20347
34228
16795
19358
39055
17874
20748
8085
25371
33809
20385
22674
1777
2761
26337
23244
33018
3026
27376
32600
6038
22197
17477
388
23977
10456
27452
6343
25010
765
9535
8908
4134
4284
3...

output:

1710307

result:

ok single line: '1710307'

Test #24:

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

input:

1000000000000 100 100 2 202
328357813456
903330009313
164185997981
231561194553
124550158519
296392508550
475599519385
900825035172
189235656551
408784569411
483033980726
336217024948
278904951489
995121215037
943411844411
156124098161
755105443489
749582869428
62956166430
689364357815
264627842323
...

output:

92553156821

result:

ok single line: '92553156821'

Test #25:

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

input:

40809 100 100 95 202
21615
6871
28286
5260
9302
25464
17992
2440
35772
13554
17596
6488
12146
39216
13766
32
13366
238
22662
4484
9536
16406
36204
23884
13786
40048
32576
9954
18238
21270
39856
19456
31780
3502
20876
10374
5124
6540
9168
4322
19070
40080
34628
39680
3726
25140
11810
12822
27570
2474...

output:

1724152

result:

ok single line: '1724152'

Test #26:

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

input:

60199 100 100 15 202
4041
4448
55152
25460
34552
13748
19810
33144
51528
17594
58602
54362
24872
23056
47096
33160
21446
27104
16400
16604
28322
1862
27114
29944
59842
45906
32172
32578
27126
52580
32584
35818
6530
28954
31380
48552
14618
53404
8966
7756
35230
45938
46344
9784
11806
20696
57260
3019...

output:

268962

result:

ok single line: '268962'

Test #27:

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

input:

65536 100 100 10 202
15719
65259
44533
65473
8864
7251
65451
60046
65487
39693
11486
56020
8259
25793
13704
62263
63674
10881
60447
14710
34657
32240
40701
65456
21157
48360
5034
26599
41306
22972
52796
6445
33850
24383
29016
49367
65452
65258
38684
56422
54809
23577
53600
35660
65469
33248
50376
40...

output:

295768

result:

ok single line: '295768'

Test #28:

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

input:

99999 100 100 245 202
17539
14516
42540
37504
57654
34480
30242
9476
3427
47782
66525
81847
21369
72772
25603
76001
50602
23184
99793
93947
16128
45765
78018
53422
70760
32260
15523
20160
79027
97982
80840
29233
98990
63503
84066
77009
89107
28628
52818
90920
2218
68744
13106
41734
54832
1211
56443
...

output:

12088526

result:

ok single line: '12088526'

Test #29:

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

input:

1000000000000 100 100 559132 202
323529417495
794117660130
676470599579
941176486281
725490208431
225490199989
274509808640
29411765389
450980399582
49019608647
352941182685
470588243446
862745112643
480392164773
656862755916
303921574034
441176478259
529411773829
823529425524
774509816672
970588251...

output:

8222537296663272

result:

ok single line: '8222537296663272'

Test #30:

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

input:

1000000000000 100 100 559132 202
794117660331
882352955701
823529425321
78431373842
941176486280
705882364758
156862747881
225490200194
656862755906
686274521297
98039217302
323529417296
588235303998
392156869609
549019617078
166666669612
205882356532
500000008634
627450990917
970588251472
490196086...

output:

8222540297522718

result:

ok single line: '8222540297522718'

Test #31:

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

input:

77777777 100 100 777777 202
1
205
409
613
817
1021
1225
1429
1633
1837
2041
2245
2449
2653
2857
3061
3265
3469
3673
3877
4081
4285
4489
4693
4897
5101
5305
5509
5713
5917
6121
6325
6529
6733
6937
7141
7345
7549
7753
7957
8161
8365
8569
8773
8977
9181
9385
9589
9793
9997
10202
10406
10610
10814
11018...

output:

602798175078

result:

ok single line: '602798175078'

Test #32:

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

input:

9999999 100 100 9999 202
8114745
1921225
982735
1324319
3187569
1402901
1284329
3785495
5348977
3374631
9315453
6890849
1966899
797523
8523823
4473119
3111439
2470293
5533827
673911
7342135
3874403
6690083
9136305
542419
4483643
1852191
1136507
607269
9020975
9532845
2715549
8555573
8420033
5752221
...

output:

49995000000

result:

ok single line: '49995000000'

Test #33:

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

input:

9999999 100 100 19600 202
2760937
1304519
4383001
2385425
8328873
4344627
2938911
1288977
1293827
8385645
3523911
9778843
5759651
5117091
9807735
8204059
4132145
1993977
8679371
3532413
7505957
389903
2825015
6727253
8409309
5595249
9138129
3767961
3038743
9128237
5867959
5630611
6070569
5414677
119...

output:

97640895969

result:

ok single line: '97640895969'

Test #34:

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

input:

100000 100 100 31 202
66008
20233
27880
96660
60745
51880
81893
82036
9567
29386
56196
60137
35604
73348
84764
96466
72291
54591
83860
37818
69653
60055
56255
51912
90778
64277
78238
96672
28164
63932
45195
31470
64496
93367
4471
20950
84791
70958
1089
31565
98661
24025
22671
51156
30821
90587
48173...

output:

783485

result:

ok single line: '783485'

Test #35:

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

input:

333333 100 100 112231 202
59631
59756
59671
59699
59661
59727
59721
59743
59604
59704
59613
59710
59718
59779
59618
59784
59626
59629
59696
59729
59766
59742
59599
59611
59711
59761
59730
59751
59670
59667
59755
59746
59662
59786
59687
59595
59737
59790
59732
59600
59775
59723
59774
59605
59607
5969...

output:

16792960744

result:

ok single line: '16792960744'

Test #36:

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

input:

50000 100 100 50 202
13807
18302
7822
41564
28370
36614
47713
45687
40814
41680
15292
42480
1856
5026
24147
18557
14602
46726
47397
48107
14881
23577
49213
38587
25723
4789
16102
15467
15544
35794
28216
34134
34612
14911
6759
32693
45269
31753
14805
48280
5515
956
24835
45259
10732
43412
35798
9237
...

output:

1215931

result:

ok single line: '1215931'

Test #37:

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

input:

50000 100 100 50 202
25546
22474
457
46882
5430
7874
32456
15680
16590
20930
1040
20627
28109
29496
44654
31602
23107
26024
19818
5021
49471
28106
7959
3350
21444
47345
39551
48660
42745
44325
39741
47544
39843
6283
28670
14657
19463
15502
18450
38489
6549
19656
14092
47259
39291
34875
35705
16887
4...

output:

1208992

result:

ok single line: '1208992'

Subtask #3:

score: 25
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #38:

score: 25
Accepted
time: 1ms
memory: 9904kb

input:

16016016 2000 2000 4161 4002
13370998
11661770
6190539
15811543
7208594
2287839
8357215
590986
15984007
9878726
4398741
1127736
11336806
461345
2915606
12889202
1514551
9872923
14002268
6698799
4382118
12385365
6011913
4440769
349275
10813747
680022
14976682
5731999
8091453
4923876
4486488
7375962
5...

output:

19783487252

result:

ok single line: '19783487252'

Test #39:

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

input:

17160249 2000 2000 5000 4002
7775887
13570785
10109057
3029521
12286149
7611815
3397711
9480753
2561297
5358697
6167103
6399221
872461
12814431
764411
7475767
6723393
11573819
6191131
14943507
13166621
9388735
4458273
12022055
10893493
7751925
2397251
15079591
3857985
11033573
10961539
9724923
13518...

output:

29961040351

result:

ok single line: '29961040351'

Test #40:

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

input:

1000000000000 2000 2000 1000000 4002
562333246111
335015960271
667985113649
58713582127
549479014215
928450409219
829996606921
163974178131
896284606361
252508483165
696482863419
932304887507
178708025383
526076766957
857178935309
962588645827
601855749519
161808011609
564446834413
22971143871
78281...

output:

3609199036570040

result:

ok single line: '3609199036570040'

Test #41:

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

input:

17000000 2000 2000 1 4002
4973616
10555439
12272010
16997605
5069646
16996623
16996532
4133345
4313406
16997085
16997323
4865582
2740878
16341404
10375374
16996699
16996648
16997506
2932941
16996886
14216670
628206
13532439
16997361
304100
8034608
11839881
8886896
1072336
16996535
16997054
12512098
...

output:

7774981

result:

ok single line: '7774981'

Test #42:

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

input:

33333333 2000 2000 16 4002
26714666
33333302
5566236
29951955
7062831
3969585
27138845
33333317
33333217
22516987
5866354
33333048
1160453
33328850
7486994
16090418
15230079
32753096
4109647
33333292
25098025
21208458
27995183
6842737
24629824
14689864
8483393
14513787
19795902
33329182
7647058
2142...

output:

242702610

result:

ok single line: '242702610'

Test #43:

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

input:

20000000 1523 1999 53 3524
19998943
4073092
7501419
19998779
14530631
10175740
13043796
472122
3974434
3340219
15932973
7772714
1229671
331192
9774059
19998871
12000880
155021
7060987
1849810
19998926
19748801
12811245
11715476
19998856
19932011
17127407
6430275
8244846
18681218
1779342
6927097
1999...

output:

529162980

result:

ok single line: '529162980'

Test #44:

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

input:

1000000000000 2000 2000 1 4002
903598441823
800701107280
329671071842
548952284792
476025051684
587913415477
417583361671
28471592560
245255301367
565935348019
528972227834
625875542896
883618376857
206793672345
212288198213
232268259154
519981190592
204795673853
385115760095
123376909148
5594418269...

output:

264699919493

result:

ok single line: '264699919493'

Test #45:

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

input:

30000000 2000 2000 1 4002
11240203
11496298
23068590
15945937
8135050
708276
22860502
29999085
7654875
2677006
27982457
28798762
5253970
11224196
17754619
28430628
29999172
4053515
14185314
10327860
11048131
19915432
19979457
21035840
6870579
2484939
22076237
11608343
17226410
8727260
804313
3957481...

output:

14501519

result:

ok single line: '14501519'

Test #46:

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

input:

100000000 2000 2000 1000000 4002
1
4005
8009
12013
16017
20021
24025
28029
32033
36037
40041
44045
48049
52053
56057
60061
64065
68069
72073
76077
80081
84085
88089
92093
96097
100101
104105
108109
112113
116117
120121
124125
128129
132133
136137
140141
144145
148149
152153
156157
160161
164165
1681...

output:

2048975001999

result:

ok single line: '2048975001999'

Test #47:

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

input:

100000000 2000 2000 36999 4002
52142059
85634799
45022505
46615303
48992493
4942481
33900955
74413203
81440717
2813425
78723363
95967983
18073057
98581293
22823435
29174611
52866453
10741403
45358705
59937993
79247645
34937503
78463257
26917499
36030055
81464763
13338719
7383745
4274193
47007551
241...

output:

1849871321738

result:

ok single line: '1849871321738'

Test #48:

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

input:

100000000000 2000 2000 5 4002
1251226705
85924799802
35070892085
64471356699
86531902907
42853724684
73376288655
23316519750
73266295012
62904323973
90088340387
37303595853
97989805937
22562534114
54446028936
1991425865
24158404559
74450205058
33605399349
84823259271
65517537521
45631354774
20786153...

output:

116663676077

result:

ok single line: '116663676077'

Test #49:

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

input:

444444444 2000 2000 444444 4002
180425991
180424741
180423839
180425173
180424088
180426059
180422588
180422561
180424451
180422996
180425852
180423910
180422177
180424430
180423854
180423217
180423845
180425957
180424274
180424050
180422630
180423034
180425958
180424023
180425306
180423614
18042553...

output:

40229664348760

result:

ok single line: '40229664348760'

Test #50:

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

input:

17000488 2000 2000 1000000 4002
13935042
6399027
2883263
2992984
9770657
4204713
12711311
12329823
8681855
316889
12449273
5146313
6247385
16212669
7468582
12780623
11480940
1833512
10221531
3696635
9608449
4296379
8832060
1830482
13448386
8830077
575096
7703266
9026723
4384485
11145642
4114150
7688...

output:

70750757930

result:

ok single line: '70750757930'

Test #51:

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

input:

17000488 2000 2000 1000000 4002
2435624
5999789
13185531
15107265
12322731
11518508
4239516
2512918
4296541
4830445
10178688
9305254
15686287
7567277
16010437
12402242
6568665
12532095
3453298
3578228
14719186
2416873
2912412
9938088
15443975
4572671
9383830
3401151
3829251
3522300
9146899
8026542
8...

output:

64567178798

result:

ok single line: '64567178798'

Subtask #4:

score: 29
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #52:

score: 29
Accepted
time: 79ms
memory: 11624kb

input:

200000000000 200000 200000 600103 400002
110104568808
171819087396
153579275763
3919156948
44861424598
186731569245
149496344510
97572698146
12915343623
73741598104
90338153812
4298821245
75793029029
22582856538
92564845068
150710592452
139824697958
162438172569
33378745268
10290539374
5613922589
13...

output:

104169813471848

result:

ok single line: '104169813471848'

Test #53:

score: 0
Accepted
time: 75ms
memory: 10020kb

input:

1000000000000 200000 200000 1000000 400002
858859094275
81875209377
616924284611
351071755357
394792773963
480713603567
347326536637
286771033863
741139705697
964192420957
207032635179
569896449491
804772423867
303209516067
990000150005
116818984123
959961199815
879935999693
938755493791
93830589154...

output:

140373567326436

result:

ok single line: '140373567326436'

Test #54:

score: 0
Accepted
time: 77ms
memory: 11572kb

input:

170000000000 200000 200000 1 400002
108815562889
101277137884
100199534273
146692489015
72365441268
66191420479
39056930202
169999671119
122742809233
93011510054
74958649831
163084543552
154156513880
169999692949
64271413962
169999678623
169999670296
169999748137
72718242411
24986883369
55019383323
...

output:

66307156091

result:

ok single line: '66307156091'

Test #55:

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

input:

170000000000 200000 200000 1 400002
169999745656
169999705954
20936869552
130641235069
135323650757
143100876780
30828502509
91078303271
23928479571
169999743226
123480811159
116211186927
50141366701
6366421036
47038156387
23867279366
169999716377
169999743213
54690581965
41010536420
127612424911
75...

output:

79106495913

result:

ok single line: '79106495913'

Test #56:

score: 0
Accepted
time: 75ms
memory: 10308kb

input:

170000000000 200000 200000 1 400002
163312544038
169999729017
169999691114
169999749459
46970956512
8693229062
169999725316
80421067905
169999689352
128373227813
128369627798
77183457095
42389341135
169999731976
83470278174
76432254639
33163710287
169999763860
169999751466
134628848609
169999742562
...

output:

84999999899

result:

ok single line: '84999999899'

Test #57:

score: 0
Accepted
time: 71ms
memory: 10112kb

input:

1000000000000 200000 200000 190 400002
3354415461
454436097684
122637365756
492391073003
253147568367
129195396061
370850911872
422955152399
844151896336
634590529350
424316758713
999999403983
608517608768
688041175852
343050783436
286600122739
35516963978
999999411068
234739883381
300446986688
4502...

output:

18151099025030

result:

ok single line: '18151099025030'

Test #58:

score: 0
Accepted
time: 75ms
memory: 11572kb

input:

200000000000 200000 200000 1 400002
84457881116
176315787219
128745228767
63999012860
181838205837
57599391558
43427344296
74014246426
52102173221
99925932787
36970122844
199999801751
166911356013
105264750709
37728525424
85433484369
199999813175
84550281396
186211020459
57434991036
63521411240
1349...

output:

99999999839

result:

ok single line: '99999999839'

Test #59:

score: 0
Accepted
time: 77ms
memory: 10348kb

input:

170000000000 200000 200000 1 400002
169999711368
31661305356
165298550912
104856749956
91158704079
105714752800
61083003744
105370351663
4460814951
40828136091
137823259609
77463058267
113446378419
169999710128
7915626337
169999678066
72633042178
133139643949
169999759146
169999706866
10110433644
96...

output:

79822469316

result:

ok single line: '79822469316'

Test #60:

score: 0
Accepted
time: 77ms
memory: 10188kb

input:

170000000000 200000 200000 1 400002
27852492544
169999718523
5208417204
169999740565
21336470857
155324116928
169999677630
116196786644
155486117496
169999693720
140942068938
24232080560
144561280865
169999757086
67243823764
150657301354
104671948251
88536694559
59776198833
132207239877
169999672355...

output:

69462719647

result:

ok single line: '69462719647'

Test #61:

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

input:

170000000000 200000 200000 1 400002
42324540682
7154823749
169999709067
169832166208
11896039475
169999756331
163203344126
84316280555
39738532086
169999733966
11011636508
169999724634
169999737236
88132293261
169999736637
169999652388
132299640940
146116487178
19261663841
66305420623
86070686403
16...

output:

79205338707

result:

ok single line: '79205338707'

Test #62:

score: 0
Accepted
time: 73ms
memory: 10200kb

input:

200000000000 200000 200000 6 400002
141998872986
196439054759
91227904152
112475174712
30885303420
199753865825
78509461731
80661468870
95808319447
155392917522
30925703566
37518925464
9790432767
69280631057
146249287011
106512355094
17503658571
24408481822
188296627627
39728932732
171872972687
3746...

output:

472143416394

result:

ok single line: '472143416394'

Test #63:

score: 0
Accepted
time: 81ms
memory: 11632kb

input:

1000000000000 200000 200000 1000000 400002
1
400005
800009
1200013
1600017
2000021
2400025
2800029
3200033
3600037
4000041
4400045
4800049
5200053
5600057
6000061
6400065
6800069
7200073
7600077
8000081
8400085
8800089
9200093
9600097
10000101
10400105
10800109
11200113
11600117
12000121
12400125
12...

output:

20004899975199999

result:

ok single line: '20004899975199999'

Test #64:

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

input:

1000000000000 200000 200000 1000000 400002
375455477269
672860164286
743642918199
514922974606
199918599593
219603898020
991570157833
337921689608
978486492417
555282776410
576472882361
308688743448
304892724469
703176315878
704920324599
272512962574
849516247577
634256371284
885258026287
9847457237...

output:

499999900013000000

result:

ok single line: '499999900013000000'

Test #65:

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

input:

400000000000 200000 200000 950 400002
111840159199
211621458105
394802774009
332122860613
77302386519
58555492788
32396961998
120271001368
388036740192
99135295694
314600373016
220432702182
66290731478
267692138482
299486697456
112430562182
289363846846
231408357072
166078030424
61565107864
36520782...

output:

189804669014079

result:

ok single line: '189804669014079'

Test #66:

score: 0
Accepted
time: 97ms
memory: 11012kb

input:

400000000000 200000 200000 900 400002
194830574149
75157975791
212298261491
153957969793
32156160789
147530737662
207133035674
356826184138
385108725552
290213451080
159177195904
380104700538
180331701680
75758378818
241647208260
125936229710
148634743204
369335046702
20878904432
2091210496
13168705...

output:

180000000000000

result:

ok single line: '180000000000000'

Test #67:

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

input:

400000000000 200000 200000 1100 400002
1822009111
146759133795
154397571989
342115710577
323700418503
71599958010
143186315942
14946474748
282219411108
44925424646
251281656424
277558587810
109220946128
366643433236
104121720636
273372566888
284401422034
97161685842
62329911686
65459127334
124800666...

output:

189993572473326

result:

ok single line: '189993572473326'

Test #68:

score: 0
Accepted
time: 94ms
memory: 11472kb

input:

400000000000 200000 200000 1800 400002
307885539421
94098070491
33724168625
338958094789
163760818809
185172925872
343554917780
331604058028
12832464180
35616178100
88075240396
323669218362
263126515652
376287481456
316210781076
165698828522
359673398392
323692818492
160231201190
375879879430
158258...

output:

190038584576031

result:

ok single line: '190038584576031'

Test #69:

score: 0
Accepted
time: 78ms
memory: 10080kb

input:

200000000000 200000 200000 1000 400002
32212702550
176635562139
182119990102
78943560403
105412536092
7228027268
45120605224
105616030516
173039559235
36039303377
106506573209
105969535551
119357273361
47447593881
23002668640
166613754396
34514854610
175091183184
104962575559
99003476804
11970742743...

output:

10025505140014

result:

ok single line: '10025505140014'

Test #70:

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

input:

200000000000 200000 200000 1000 400002
153663017314
12581997016
24891484751
78656996690
76627767203
2455312311
75594058795
145430070322
129893583475
185588098056
40484545827
152008483396
192668974080
87865251688
74362659995
141841563338
15462257269
167519599853
75364552815
68798438015
21292698889
10...

output:

10040242849536

result:

ok single line: '10040242849536'

Test #71:

score: 0
Accepted
time: 82ms
memory: 10348kb

input:

200000000000 200000 200000 1000 400002
192939170799
32217663815
178255477632
128170519966
196753834305
138481988640
51548377075
123211604517
78488161665
103350298426
75975095256
27386415424
76483272911
87053558559
178751863396
175718372701
168664586366
173850832908
184624556511
61941368526
120765845...

output:

10478774982465

result:

ok single line: '10478774982465'

Test #72:

score: 0
Accepted
time: 78ms
memory: 10368kb

input:

200000000000 200000 200000 1000 400002
129177114545
126499345946
120670053787
192741017623
125297279227
186735364939
183532733067
112090718605
32250779428
14341247899
184496501327
150535652394
155252223578
50145836218
115850572674
179634337394
186236142542
90614368695
120565255450
14518051822
109859...

output:

13715494706929

result:

ok single line: '13715494706929'

Test #73:

score: 0
Accepted
time: 75ms
memory: 10068kb

input:

200000000000 200000 200000 1000 400002
19572847485
20805453487
151605090802
131716327165
100967364150
40249547041
194794559890
198813790649
169031810455
104418760411
51575201343
93588880320
123315450331
103362820592
195382848953
134078198882
44165027053
189450052370
112347369366
134896601892
1682323...

output:

31325103176701

result:

ok single line: '31325103176701'

Test #74:

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

input:

200000000000 200000 200000 1000 400002
45906569177
127728588007
193327197727
96017504291
151709655403
23482355022
43719244839
174011044164
52216455689
47088814963
172154245379
126433385100
167267628415
1031257693
185921264880
11782987624
115450815783
31192677833
143859095285
64704011512
147217657866...

output:

63743950940997

result:

ok single line: '63743950940997'

Test #75:

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

input:

200000000000 200000 200000 1000 400002
151300352413
143801686847
21465873725
138016128706
124872256541
137682867229
185404014327
33531138729
169433648728
48842843023
94314139596
178679399132
161019321014
198581383017
51852887220
196847576168
38379104761
154266076077
132684208588
65116442814
70999675...

output:

92372468373112

result:

ok single line: '92372468373112'

Test #76:

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

input:

200000000000 200000 200000 1000 400002
85414871981
126917682658
33946759408
48839151973
72146589469
88103853822
104993639034
33387005053
167620915648
12460321043
18467672488
187222631200
25403481058
30230646517
86021984031
51187358055
89533576298
3582443438
15280709827
76549135585
140220518437
12101...

output:

99998408211058

result:

ok single line: '99998408211058'

Test #77:

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

input:

222222222222 200000 200000 1000 400002
69234853422
69234856118
69235052340
69234764130
69235075453
69234864531
69234789632
69235039591
69235001236
69234970849
69235024950
69235102506
69234826115
69234857683
69234954100
69234806546
69234978493
69234793398
69234996227
69234781642
69235012306
692351238...

output:

44638735419846

result:

ok single line: '44638735419846'

Test #78:

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

input:

222222222222 200000 200000 1000 400002
206263373934
206263143831
206263239487
206263204553
206263261597
206263381053
206263271180
206263082774
206263269911
206263411813
206263054768
206263068653
206263225878
206263305128
206263421138
206263150330
206263078536
206263369896
206263051415
206263206768
2...

output:

110452793598584

result:

ok single line: '110452793598584'

Test #79:

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

input:

222222311099 200000 200000 1000000 400002
155810837092
48811013365
56186317569
177779892671
167036923689
66674762708
6133487333
132969318758
163901659086
217167415562
61703253093
712399518
66562586492
111043030227
66258953441
196006510567
12446238136
83731810354
127922944342
40350100558
110524465664...

output:

9791570077751

result:

ok single line: '9791570077751'

Test #80:

score: 0
Accepted
time: 78ms
memory: 10064kb

input:

222222311099 200000 200000 1000000 400002
51526976536
12711521830
200744558232
194140398085
147509495894
53106360703
194631110239
178955074434
33619498834
203719230056
28385639724
92821360886
118561963279
106534676999
143303457347
190076004179
193581225537
57485089525
42833303016
210547481875
422669...

output:

8168746223892

result:

ok single line: '8168746223892'

Extra Test:

score: 0
Extra Test Passed