QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#417079#1454. Um nik's AlgorithmqiuzxAC ✓3540ms290848kbC++203.0kb2024-05-22 14:05:402024-05-22 14:05:41

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 87076kb

input:

3 2 4
1 1
2 1
3 1
3 2

output:

2
2
4

result:

ok answer: 2, maximum: 2

Test #2:

score: 0
Accepted
time: 3ms
memory: 86932kb

input:

20 20 20
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20

output:

20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

result:

ok answer: 20, maximum: 20

Test #3:

score: 0
Accepted
time: 11ms
memory: 88824kb

input:

1000 1000 10000
988 405
844 805
40 354
416 591
520 704
697 24
315 386
122 390
991 213
506 14
309 298
26 829
329 63
787 91
971 703
805 699
624 645
121 181
841 741
473 84
258 116
490 753
725 603
265 302
869 71
611 507
59 292
11 532
117 61
192 600
650 342
204 580
687 675
670 407
637 622
569 236
728 476...

output:

1000
8
13
18
32
36
40
44
52
56
64
72
79
82
99
103
145
153
164
175
179
189
194
196
202
220
237
240
247
265
272
306
316
318
322
323
324
326
329
336
348
350
351
358
365
389
391
393
411
436
440
441
449
451
456
458
459
463
475
487
493
499
502
511
514
532
533
536
537
538
555
571
575
583
592
620
631
636
64...

result:

ok answer: 1000, maximum: 1000

Test #4:

score: 0
Accepted
time: 7ms
memory: 85288kb

input:

100 2 200
40 1
22 2
75 2
79 1
27 2
11 1
7 1
64 1
21 1
57 2
47 1
4 2
61 2
37 1
8 2
32 2
84 1
63 1
67 1
86 2
88 2
73 1
17 1
94 2
44 2
19 2
16 1
33 2
92 1
24 2
100 2
18 2
85 1
7 2
43 1
82 2
15 2
88 1
91 1
65 1
69 1
36 1
6 2
23 2
58 1
59 1
64 2
38 1
72 1
99 1
76 1
11 2
2 2
98 1
66 2
77 1
47 2
98 2
52 2
...

output:

2
31
50

result:

ok answer: 2, maximum: 2

Test #5:

score: 0
Accepted
time: 3ms
memory: 86676kb

input:

1000 1000 1000
411 789
753 186
495 203
417 324
490 424
195 480
314 23
663 218
12 747
124 390
134 38
218 536
291 840
174 908
474 767
313 167
575 9
857 427
313 27
959 935
258 70
472 957
747 228
205 939
293 303
626 802
712 283
658 346
208 383
889 204
99 640
801 966
828 742
534 11
259 734
226 129
843 35...

output:

540
1
2
3
5
6
7
11
17
18
21
22
23
25
30
31
33
34
37
39
42
43
44
45
46
47
48
49
50
51
52
55
58
59
60
61
62
63
66
67
69
70
73
74
75
76
77
78
80
84
85
88
89
90
92
94
95
96
97
100
103
107
108
111
113
114
117
119
121
122
124
125
129
130
131
132
135
139
140
143
144
148
150
151
155
157
161
162
163
165
166
...

result:

ok answer: 540, maximum: 540

Test #6:

score: 0
Accepted
time: 9ms
memory: 85172kb

input:

1000 2000 3000
143 619
571 526
215 1074
6 1714
370 937
120 784
134 1671
722 1528
397 345
464 401
198 589
283 564
212 232
527 286
237 1649
413 1570
964 1731
194 645
639 735
182 656
641 1143
535 98
113 596
787 972
306 818
657 1202
321 1327
753 1088
122 1823
471 611
516 811
380 1548
872 973
509 1841
70...

output:

944
1
9
11
16
17
18
26
32
33
37
40
41
46
53
54
55
60
61
63
65
68
69
73
75
77
79
81
84
86
91
94
99
100
104
105
113
115
118
123
126
127
139
141
142
155
156
162
166
167
168
169
176
178
179
181
182
187
201
202
204
213
216
219
222
225
227
233
236
241
244
247
248
261
268
269
270
271
272
275
276
281
282
28...

result:

ok answer: 944, maximum: 944

Test #7:

score: 0
Accepted
time: 3540ms
memory: 285980kb

input:

2000000 2000000 2000000
1203137 1030076
215220 238101
293102 491863
1260446 165178
1683989 1718181
1641329 1179380
708733 403707
1918936 574923
525651 11571
1169951 422281
1086376 303530
1286459 1692862
31854 394688
916288 273853
709758 1176923
1730408 1766172
1890708 588004
344339 283448
1676753 13...

output:

1088264
1
2
6
7
8
10
11
12
15
18
23
25
27
29
30
31
34
35
36
38
39
40
41
42
43
44
45
47
51
56
57
58
59
60
61
62
63
66
67
68
71
74
78
80
81
84
86
88
89
92
93
94
95
96
97
98
102
103
104
105
107
111
113
114
116
117
118
119
120
121
125
126
128
129
131
132
134
135
138
140
141
143
148
150
155
157
159
160
1...

result:

ok answer: 1088264, maximum: 1088264

Test #8:

score: 0
Accepted
time: 3350ms
memory: 287248kb

input:

2000000 2000000 2000000
1286561 1611624
1028477 1867578
1642356 1162128
1032429 316462
618144 22363
1644873 1514932
508824 1230141
1889259 22840
30270 259129
1567969 462330
150124 1227115
393968 534541
1378415 770304
977805 1666010
1199878 1476793
1249634 243739
1232999 531436
1146447 1845344
478779...

output:

1088047
1
2
3
4
8
9
14
15
17
20
22
24
25
30
34
37
38
39
42
43
46
47
48
50
51
53
56
62
64
70
71
72
73
74
75
76
77
78
79
80
84
87
89
91
92
93
95
97
100
101
102
103
105
107
108
110
113
114
115
116
117
119
120
122
123
128
130
131
132
134
137
138
139
140
142
145
146
147
148
149
150
151
152
153
155
157
15...

result:

ok answer: 1088047, maximum: 1088048

Test #9:

score: 0
Accepted
time: 3534ms
memory: 288696kb

input:

2000000 2000000 2000000
402689 127765
1065927 1753952
991609 1640904
1061308 533154
1552300 326545
1905312 1074675
1084722 1799678
51070 1470757
310696 763584
1965988 759275
246577 1374893
277285 408924
1692272 1856320
72026 1123575
1881487 1519767
1993052 1562521
575291 1507572
205452 248456
134621...

output:

1087919
2
3
4
5
7
10
11
12
14
15
17
19
24
25
26
32
33
34
37
39
40
41
44
45
46
47
49
50
51
52
53
56
60
61
65
66
67
70
71
74
79
80
81
82
83
84
85
87
88
91
93
96
97
99
100
102
103
105
106
107
109
111
114
115
116
117
118
119
120
121
124
125
127
128
129
130
132
134
136
137
138
140
142
145
146
147
148
152...

result:

ok answer: 1087919, maximum: 1087919

Test #10:

score: 0
Accepted
time: 3050ms
memory: 288104kb

input:

2000000 2000000 2000000
486113 452417
846481 1383429
1116671 119681
1800588 1717142
294967 630728
1198456 1601715
884812 626111
1054097 142866
782611 1978438
1396710 1832027
534517 555375
417499 1250604
6129 166529
1166247 772627
371607 1819638
1512279 1072791
884878 1451005
1974857 843056
213647 10...

output:

1088039
1
2
3
6
8
10
11
12
16
18
19
25
26
28
30
31
35
36
37
39
41
43
47
48
49
52
53
55
56
58
60
61
62
63
64
66
67
68
69
71
75
76
77
79
80
81
82
92
95
96
97
102
103
104
105
106
107
108
113
114
115
116
117
118
119
120
121
122
123
124
125
127
129
131
132
133
134
137
138
139
140
142
143
144
145
147
148
...

result:

ok answer: 1088039, maximum: 1088039

Test #11:

score: 0
Accepted
time: 3305ms
memory: 288288kb

input:

2000000 2000000 2000000
569537 968557
1851226 45611
465925 789946
605275 1868426
261827 934910
1458895 1161459
684902 1195648
1215908 623487
30333 482892
827432 1096268
1598266 1478961
1525008 349179
385394 476737
1227764 164784
85919 119508
255697 326166
1970273 1394437
1809670 1180760
1015672 2547...

output:

1088084
1
2
4
8
9
11
13
14
15
17
19
20
21
22
25
26
30
31
34
36
37
38
41
42
43
45
47
50
51
53
54
56
58
59
60
61
63
64
66
67
68
72
73
77
81
82
89
96
98
100
101
103
107
108
110
112
114
117
118
119
121
124
125
126
129
130
132
135
136
137
139
142
143
148
150
152
154
155
156
158
162
164
168
169
170
171
17...

result:

ok answer: 1088084, maximum: 1088084

Test #12:

score: 0
Accepted
time: 3062ms
memory: 288472kb

input:

2000000 2000000 2000000
1685665 517402
664484 1675089
782474 1268723
1601450 85118
1195982 1239092
752039 721202
484993 1054786
218935 71404
310760 730450
1225450 1393213
662014 594034
632517 223562
699251 595457
321985 846541
576040 1386674
1774923 1836436
1312564 1337869
868675 808065
1107298 1517...

output:

1087210
2
3
4
14
15
17
19
20
21
22
23
27
28
29
30
32
34
38
39
41
42
44
46
47
48
51
52
54
56
57
58
59
60
62
63
64
66
68
70
74
75
77
79
81
86
87
89
90
92
93
94
95
98
99
100
103
105
106
107
109
110
111
115
116
118
121
123
128
138
139
140
142
145
146
147
151
153
154
155
156
159
160
161
162
165
169
172
1...

result:

ok answer: 1087210, maximum: 1087210

Test #13:

score: 0
Accepted
time: 1952ms
memory: 290156kb

input:

2000000 2000000 2000000
671367 438853
664485 1398539
742842 386640
982299 485454
546419 1461681
1152709 654964
1250048 1661588
622998 536507
189300 1149326
1931736 1799077
327683 1819025
1040667 1571337
868282 1226836
498815 773984
808618 988294
712394 173925
134058 436291
98285 443781
1609589 78910...

output:

1535209
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
27
28
30
32
33
35
36
37
38
39
41
42
44
46
47
49
50
51
52
53
54
55
56
57
59
60
61
63
64
65
66
68
69
71
72
73
74
75
77
79
80
81
82
83
84
85
87
88
89
90
92
93
95
96
97
100
102
104
105
106
107
109
110
111
112
113
114
115
116
118
1...

result:

ok answer: 1535209, maximum: 1535209

Test #14:

score: 0
Accepted
time: 1496ms
memory: 288908kb

input:

2000000 2000000 2000000
138574 1342064
1643595 562587
1113082 1866381
1046781 69854
1995906 718620
1878456 1065477
1148129 1000230
128358 393159
1893827 365760
1922621 1583574
868735 553414
1400420 471921
147059 404788
1439120 680482
225083 1540271
1016807 1950769
1635754 371279
967724 1695575
13292...

output:

1802113
1
2
5
6
7
8
9
10
11
12
14
15
16
17
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
94
95
96
97
98
99
100
101
102
103
104
105...

result:

ok answer: 1802113, maximum: 1802113

Test #15:

score: 0
Accepted
time: 1234ms
memory: 288868kb

input:

2000000 2000000 2000000
536222 1734576
23820 45248
833336 1030570
413414 1449610
1303634 31529
1081756 593258
988649 183711
216216 1083600
127109 1327665
1021151 187582
712397 68980
1201276 912972
579821 1496356
516811 165481
829561 433889
116397 1703535
41995 1565188
452103 1023063
124730 1958243
2...

output:

1900296
1
2
3
4
5
6
7
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
31
32
33
34
35
36
37
38
39
40
41
42
43
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
99
100
101
102
103...

result:

ok answer: 1900296, maximum: 1900296

Test #16:

score: 0
Accepted
time: 640ms
memory: 290520kb

input:

2000000 2000000 2000000
722296 810199
1104653 1326072
1384593 1991732
1359998 1074298
1745667 1702626
1958690 1040248
741056 1119935
123334 480039
941370 1134989
1340612 1877995
1628998 735318
1713870 573904
179004 731624
244572 1375222
1938456 934124
429528 1129329
655320 133186
1680525 1039251
180...

output:

1999999
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
...

result:

ok answer: 1999999, maximum: 1999999

Test #17:

score: 0
Accepted
time: 429ms
memory: 279140kb

input:

2000000 2000000 2000000
1047606 1292677
12506 1323616
1342868 93241
104701 1762734
1092674 826296
832718 320225
1030367 1004288
1092277 1855541
1147594 1592403
344053 1265006
957034 1327349
1581922 1471180
1394689 1275806
347140 757111
1968638 1065864
1735165 801763
916090 1855541
1294013 117591
177...

output:

38
80694
111252
130534
133699
202799
228363
273320
282877
312955
397617
445573
455247
509969
584664
661015
674635
710589
782456
915823
1096601
1103323
1129875
1161601
1178857
1260088
1292643
1319191
1347247
1349480
1393141
1455891
1506241
1535149
1560772
1613630
1689211
1810122
1814857

result:

ok answer: 38, maximum: 38

Test #18:

score: 0
Accepted
time: 301ms
memory: 278320kb

input:

2000000 2000000 2000000
1873411 1383547
592374 1383547
837927 228335
880140 1383547
117684 1383547
873521 1383547
1659145 1383547
837927 1940103
684954 1383547
837927 649822
837927 553974
837927 263980
837927 1851187
645118 1383547
837927 536305
1931765 1383547
960556 1383547
837927 741946
837927 18...

output:

2
1724149
1778614

result:

ok answer: 2, maximum: 2

Test #19:

score: 0
Accepted
time: 262ms
memory: 280244kb

input:

2000000 2000000 2000000
679516 1758922
654113 491405
679516 903481
679516 1931142
1695416 491405
1087335 491405
679516 209225
991588 491405
679516 1423758
679516 1731533
815888 491405
84804 491405
679516 614525
532920 491405
679516 1583057
852179 491405
679516 641320
679516 158707
679516 883286
6795...

output:

2
550532
643309

result:

ok answer: 2, maximum: 2

Test #20:

score: 0
Accepted
time: 483ms
memory: 279552kb

input:

2000000 2000000 2000000
950672 1358549
1019276 293
1341818 453182
517288 976497
1157473 567426
1601935 896019
1434229 1234860
1822883 1319667
1174043 794189
815886 186003
1433841 238760
599172 90292
1139073 538283
1651444 1723218
1890294 90292
749958 1255878
1584651 934604
31690 1957346
582723 18920...

output:

444
1477
8830
13228
24050
31257
35139
36897
38242
39259
42990
44389
49408
51853
53332
54923
57833
60663
67806
69395
77341
80694
82684
88070
91463
98004
110825
111252
117201
129629
132908
139739
139879
140572
149103
149699
158341
164057
169023
172828
181920
186320
192290
192545
199225
199638
201370
2...

result:

ok answer: 444, maximum: 444

Test #21:

score: 0
Accepted
time: 7ms
memory: 94048kb

input:

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

output:

32
23
62
90
124
157
178
224
246
275
312
351
379
404
433
469
505
524
537
551
566
581
607
619
627
653
670
676
689
714
722
744
768

result:

ok answer: 32, maximum: 32

Test #22:

score: 0
Accepted
time: 321ms
memory: 160692kb

input:

1632 1632 1997568
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1...

output:

1632
956
3128
4526
6346
8118
9309
11388
12942
14294
16102
17837
19015
20475
22423
24222
26029
26964
29202
30880
32080
34049
35641
37192
38556
40144
42219
43509
45248
47050
48316
49863
51692
53067
55169
56458
58719
59730
61769
62970
64533
66774
68341
70105
71200
73069
74867
76062
78038
79492
81555
82...

result:

ok answer: 1632, maximum: 1632

Test #23:

score: 0
Accepted
time: 7ms
memory: 90016kb

input:

189 189 19845
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
...

output:

189
67
230
355
487
592
715
880
953
1114
1255
1342
1463
1614
1710
1887
1960
2089
2240
2349
2506
2594
2737
2889
2977
3125
3219
3401
3502
3592
3750
3894
3982
4148
4276
4383
4523
4622
4759
4863
5022
5159
5258
5418
5511
5631
5759
5862
6006
6126
6289
6411
6533
6642
6772
6899
7013
7166
7287
7428
7499
7640
...

result:

ok answer: 189, maximum: 189

Test #24:

score: 0
Accepted
time: 487ms
memory: 160356kb

input:

1896 1896 1997120
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1...

output:

1896
1143
2440
3419
4852
6197
7261
8764
9927
11015
12107
13491
14907
16010
17165
18557
20157
20980
22572
23506
25067
26507
27273
28933
30000
31214
32675
33690
34813
36052
37414
38559
40246
41698
42555
44211
45005
46188
47604
48985
50275
51811
52472
53827
55323
56733
57861
59111
60532
61337
62604
641...

result:

ok answer: 1896, maximum: 1896

Test #25:

score: 0
Accepted
time: 669ms
memory: 276116kb

input:

2000000 2000000 1997120
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
...

output:

1896
1143
2440
3419
4852
6197
7261
8764
9927
11015
12107
13491
14907
16010
17165
18557
20157
20980
22572
23506
25067
26507
27273
28933
30000
31214
32675
33690
34813
36052
37414
38559
40246
41698
42555
44211
45005
46188
47604
48985
50275
51811
52472
53827
55323
56733
57861
59111
60532
61337
62604
641...

result:

ok answer: 1896, maximum: 1896

Test #26:

score: 0
Accepted
time: 885ms
memory: 275456kb

input:

2000000 2000000 2000000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
...

output:

183937
812
2204
3028
4581
5802
6856
8150
9562
10590
11624
12940
13850
15116
16606
17499
18811
20358
21410
22671
23987
24942
25935
27052
28779
29468
30938
31802
33270
34551
35752
36840
38331
39259
40642
41546
42703
44061
45053
46577
47913
48964
50289
51207
52390
53598
54963
56278
57487
58732
59737
60...

result:

ok answer: 183937, maximum: 183937

Test #27:

score: 0
Accepted
time: 939ms
memory: 273804kb

input:

2000000 2000000 2000000
513 1122
1458 523
325 794
1951215 1284660
33 326
361 381
967 990
554 329
1682 399
250 704
294 196
520 496
976 939
583 776
689 1048
163 262
884 889
1147 1673
1552 459
1097 1091
826436 1860
255 516
1640 446
1643 55
1028 1318
1307752 1431867
716 1405
264 671
1018 1511
1798 413
1...

output:

184175
4
21
39
57
60
64
74
77
91
108
131
135
136
139
154
198
209
231
269
278
317
325
331
334
335
365
379
396
412
418
426
428
431
440
444
451
460
461
462
473
483
498
509
528
529
535
536
574
602
605
608
620
635
646
662
664
698
706
707
734
736
781
802
809
820
821
826
856
879
908
910
911
921
931
945
948...

result:

ok answer: 184175, maximum: 184175

Test #28:

score: 0
Accepted
time: 1101ms
memory: 277444kb

input:

2000000 2000000 2000000
318377 264230
318377 297294
318377 1168121
318377 1168378
318377 687841
318377 317579
318377 1045281
318377 193774
318377 1286449
318377 809491
318377 305478
318377 1431410
318377 173240
318377 1833841
318377 824344
318377 722522
318377 1887702
318377 1302344
318377 864333
31...

output:

183975
730
2356
3055
4727
5742
6696
8147
9595
10562
11680
13136
14211
15106
16623
17739
18719
20305
21379
22253
23573
24892
26381
27146
28663
29512
31045
32314
33567
34551
35745
36897
38036
39259
40308
41872
43003
44118
45317
46398
47949
48964
50191
51453
52379
53465
54883
56028
57416
58772
59865
60...

result:

ok answer: 183975, maximum: 183975

Test #29:

score: 0
Accepted
time: 1129ms
memory: 277224kb

input:

2000000 2000000 2000000
1625116 599613
539469 1308455
812983 176633
874289 461823
1824953 1589033
794027 1271010
178174 1700721
1161616 1322163
1277276 32631
1962706 1017199
282239 1158238
1206051 966351
1745846 987176
361370 985866
857047 470035
637002 976591
1362011 429199
1160438 673497
1007777 1...

output:

184156
22
23
32
45
60
63
71
73
101
107
110
140
161
182
202
206
211
218
228
241
266
278
282
297
302
310
318
324
329
332
350
361
362
370
386
399
401
408
409
420
425
426
439
450
456
469
510
517
519
536
558
564
572
577
579
587
611
614
621
625
631
637
645
656
670
690
730
737
743
748
759
762
771
777
783
7...

result:

ok answer: 184156, maximum: 184156

Test #30:

score: 0
Accepted
time: 711ms
memory: 276312kb

input:

2000000 2000000 2000000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
...

output:

11043
659
2029
3379
5020
5956
7009
8504
9525
10919
12544
13706
15106
16151
17480
18857
19997
20835
22537
23476
24663
26409
27744
28742
30232
31173
32468
33675
34803
36208
37391
38869
39941
41400
42320
43822
45248
46157
47398
49194
50172
51349
52939
53910
55347
56226
57861
58776
60527
61211
62713
642...

result:

ok answer: 11043, maximum: 11043

Test #31:

score: 0
Accepted
time: 647ms
memory: 276332kb

input:

2000000 2000000 2000000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
...

output:

4770
719
2031
3702
4829
5956
7008
8531
9927
11261
12285
13630
15106
15884
17078
18439
20025
21168
22175
23476
25034
26106
27598
28823
30046
31214
32514
34059
34993
36248
37402
39002
40293
41676
42555
43838
45200
46659
47404
48733
50275
51527
52493
54315
55399
56301
57879
59238
60658
61417
62875
6415...

result:

ok answer: 4770, maximum: 4770

Test #32:

score: 0
Accepted
time: 619ms
memory: 276652kb

input:

2000000 2000000 2000000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
...

output:

1505
579
1889
2654
3633
4554
5569
6748
7968
8793
9572
10609
11638
12695
13922
14944
15731
16548
17565
18594
19583
20876
21664
22855
23891
24643
25884
26878
27722
28595
29980
30888
31620
32574
33791
34656
35963
36840
37637
38661
39740
40838
41671
42703
43822
44830
45897
46959
47573
48581
49896
50766
...

result:

ok answer: 1505, maximum: 1505

Test #33:

score: 0
Accepted
time: 655ms
memory: 274664kb

input:

2000000 2000000 2000000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
...

output:

1804
812
2204
3028
4581
5802
6856
8150
9562
10590
11624
12940
13850
15116
16606
17499
18811
20358
21410
22671
23987
24942
25935
27052
28779
29468
30938
31802
33270
34551
35752
36840
38331
39259
40642
41546
42703
44061
45053
46577
47913
48964
50289
51207
52390
53598
54963
56278
57487
58732
59737
6060...

result:

ok answer: 1804, maximum: 1804

Test #34:

score: 0
Accepted
time: 585ms
memory: 274540kb

input:

2000000 2000000 2000000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
...

output:

1356
828
1639
2356
3552
4219
5360
6212
6916
7811
8627
9474
10587
11380
12526
13462
14303
15116
15900
16765
17593
18470
19464
20318
21584
22150
22953
23891
25173
25847
26764
27877
28407
29295
30261
31112
32281
33249
34000
34885
35651
36621
37640
38559
39523
40308
41255
42271
42881
43865
44622
45737
4...

result:

ok answer: 1356, maximum: 1356

Test #35:

score: 0
Accepted
time: 502ms
memory: 275208kb

input:

2000000 2000000 2000000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
...

output:

1051
359
1164
1775
2599
3326
3994
4720
5573
6212
6789
7581
8325
8794
9735
10202
11091
11713
12285
13239
13861
14451
15171
16066
16618
17307
18153
18886
19464
20197
20717
21681
22303
22925
23701
24492
24872
25847
26419
27052
27780
28663
29326
29966
30543
31449
32195
32616
33274
34183
34950
35657
3611...

result:

ok answer: 1051, maximum: 1051

Test #36:

score: 0
Accepted
time: 898ms
memory: 273728kb

input:

2000000 2000000 2000000
1410388 834484
1410388 239410
1410388 1232286
1410388 207365
1410388 1395003
1410388 1968948
1410388 576378
1410388 76728
1410388 1644827
1410388 1278820
1410388 593448
1410388 904665
1410388 1931363
1410388 1889040
1410388 1147950
1410388 218013
1410388 1688590
1410388 13887...

output:

1651
1042
2160
3071
4040
5232
6434
7322
8482
9468
10599
11680
13136
14211
15070
16066
17416
18455
19789
20425
21501
22831
23943
25012
26363
27184
28286
29257
30305
31384
32821
34034
34658
35786
36897
38242
39519
40391
41773
42839
43937
44717
45692
47137
48185
49485
50300
51560
52379
53465
54646
5602...

result:

ok answer: 1651, maximum: 1651

Test #37:

score: 0
Accepted
time: 985ms
memory: 273680kb

input:

2000000 2000000 2000000
1686157 1036655
905644 1257773
231391 1553076
1776476 17761
1718008 397514
1502594 1699978
1112572 590070
1128891 1730637
1547654 1908592
1182198 717510
645722 749840
1307572 1364844
1466826 1763992
373885 1613469
12498 321213
265420 1503625
574762 197883
654547 1390192
19624...

output:

1365
975
982
2160
2390
4198
4341
7014
7982
10697
12545
14252
14355
14725
15644
20025
20850
21356
22253
25332
26689
28384
29848
31035
31384
31449
34183
35745
44348
46477
47271
48777
49331
51578
52513
52524
53338
54683
58634
59957
60604
60631
62214
63576
67323
69922
70974
72304
76062
76196
77341
79014...

result:

ok answer: 1365, maximum: 1365

Test #38:

score: 0
Accepted
time: 645ms
memory: 274920kb

input:

2000000 2000000 2000000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
...

output:

1515
579
1889
2654
3633
4554
5569
6748
7968
8793
9572
10609
11638
12695
13922
14944
15731
16548
17565
18594
19583
20876
21664
22855
23891
24643
25884
26878
27722
28595
29980
30888
31620
32574
33791
34656
35963
36840
37637
38661
39740
40838
41671
42703
43822
44830
45897
46959
47573
48581
49896
50766
...

result:

ok answer: 1515, maximum: 1515

Test #39:

score: 0
Accepted
time: 3416ms
memory: 274440kb

input:

2000000 2000000 2000000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
...

output:

2522
35426
36259
37074
37862
38641
39475
40293
41096
41875
42712
43493
44279
45109
45909
46739
47500
48322
49136
49929
50727
51523
52379
53185
53994
54742
55582
56411
57194
58000
58772
59606
60386
61253
62031
62823
63672
64435
65277
66020
66829
67673
68457
69251
70085
70856
71658
72528
73323
74069
7...

result:

ok answer: 2522, maximum: 2565

Test #40:

score: 0
Accepted
time: 3294ms
memory: 273228kb

input:

2000000 2000000 2000000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
...

output:

2946
52954
53996
54977
55955
56964
57976
58984
59953
60979
61975
62970
63960
64980
65960
67000
67997
68984
69959
70983
71975
72949
73936
74997
75951
76987
77957
78991
79989
80961
81966
82975
83967
84986
85922
86999
87924
88926
89998
90912
91999
92935
93924
94983
95908
96999
97911
98942
99982
100919
...

result:

ok answer: 2946, maximum: 2998

Test #41:

score: 0
Accepted
time: 3404ms
memory: 274308kb

input:

2000000 2000000 2000000
194151 1938743
219729 1342843
68564 86794
693354 1338943
702775 386871
836157 501653
625353 1528914
1202559 373185
1190037 460020
109144 7201
1509959 1182372
1303399 1859980
281937 429619
1375375 1140805
1967865 1423773
274895 820740
86914 1312016
745802 1304378
1383905 79192...

output:

2946
1235
1361
3003
3791
3802
4142
4326
7575
7610
7828
8650
8679
10069
10976
13378
13387
15100
17117
17937
20166
20996
21031
22109
22175
24130
25438
26172
26230
27146
28606
29120
29533
29551
31070
32754
33411
33752
33801
34104
34150
34314
34440
36067
36289
36523
37637
39532
40006
41255
42280
42499
4...

result:

ok answer: 2946, maximum: 2998

Test #42:

score: 0
Accepted
time: 3294ms
memory: 275288kb

input:

2000000 2000000 2000000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
...

output:

2662
44118
45024
45938
46842
47735
48641
49506
50430
51302
52215
53150
54034
54929
55809
56733
57636
58512
59404
60359
61214
62111
63003
63916
64860
65726
66670
67558
68457
69348
70264
71121
72061
72932
73819
74739
75671
76523
77482
78343
79272
80137
81069
81910
82886
83781
84675
85528
86407
87313
8...

result:

ok answer: 2662, maximum: 2710

Test #43:

score: 0
Accepted
time: 3244ms
memory: 276008kb

input:

2000000 2000000 2000000
808248 552259
667514 1319054
1871613 39928
967451 1289759
121536 839484
1144906 293777
953710 1302471
926057 1130229
1971166 1472560
570716 319665
993182 847647
503839 1448077
1477180 1090769
866885 830795
825148 986508
1855201 601420
425225 1209935
1327152 158029
1750913 134...

output:

2753
97
128
316
979
1281
1416
1767
2876
4471
4963
5784
6050
7014
7058
7664
10785
11458
11958
12054
13357
13711
15106
16444
16696
18120
18549
18571
19352
20733
21346
21603
21887
22812
24036
24050
24418
25094
25261
26870
28321
29028
30501
31280
31857
34680
35845
36130
36366
36380
36821
37337
39015
402...

result:

ok answer: 2753, maximum: 2800

Test #44:

score: 0
Accepted
time: 3454ms
memory: 273564kb

input:

2000000 2000000 2000000
718302 630746
525264 939615
1513350 1873077
423465 103470
951359 287841
279717 1446774
333123 1231534
1505351 1924842
373931 77349
1219573 981167
406220 1773980
900787 835783
1382738 581012
1073706 1285129
945967 1563314
1701380 1449817
1653881 342722
1239856 1648628
1205777 ...

output:

2705
185
1468
1769
2503
3142
3154
4235
4242
5312
5920
6130
6137
6139
6634
7014
8186
8865
10110
10302
10452
11362
12285
12456
13100
15045
16114
17174
17512
18930
19593
20425
20493
21864
22488
22714
23556
23682
24634
24721
24727
25297
25551
25814
26868
28367
28466
28791
29268
31384
31973
32061
32107
3...

result:

ok answer: 2705, maximum: 2750

Test #45:

score: 0
Accepted
time: 3256ms
memory: 275092kb

input:

2000000 2000000 2000000
1047008 1232125
151532 351751
52892 1005841
286679 1721611
1079778 897632
1546359 822542
1525784 480194
543504 476429
289791 1740845
1120554 931051
1115547 42416
776964 774892
332228 1748138
871235 93456
992460 173688
996367 275112
1753268 895023
1559974 1826000
527625 155211...

output:

2488
65
515
788
982
1257
1700
1747
4485
4650
4744
4983
5382
5863
6534
7063
7260
7282
7655
7704
8116
8510
8896
10951
11082
12850
12955
13147
15529
15542
16461
16902
17609
18393
19851
20664
20844
20955
21739
22192
22484
22545
24702
25150
25605
26714
27568
28482
29601
29680
30732
31924
32608
33586
3433...

result:

ok answer: 2488, maximum: 2530

Test #46:

score: 0
Accepted
time: 3281ms
memory: 276072kb

input:

2000000 2000000 2000000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
...

output:

2365
29606
30411
31209
32008
32804
33612
34407
35239
36024
36840
37637
38443
39201
40027
40848
41641
42432
43233
44046
44830
45614
46417
47225
48021
48815
49662
50403
51261
52016
52826
53619
54449
55255
56059
56860
57650
58457
59220
60071
60822
61663
62476
63228
64013
64864
65681
66423
67254
68042
6...

result:

ok answer: 2365, maximum: 2401

Test #47:

score: 0
Accepted
time: 3388ms
memory: 274520kb

input:

2000000 2000000 2000000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
...

output:

1930
19240
19854
20469
21088
21734
22337
22944
23573
24205
24815
25441
26072
26689
27287
27902
28550
29173
29778
30383
31045
31648
32278
32899
33491
34150
34776
35346
35983
36622
37252
37871
38450
39095
39726
40331
40984
41566
42172
42849
43436
44061
44711
45317
45945
46566
47136
47789
48437
49039
4...

result:

ok answer: 1930, maximum: 1960

Test #48:

score: 0
Accepted
time: 432ms
memory: 281628kb

input:

2000000 2000000 1978001
1 490000
490001 1
2 489999
490001 2
3 489998
490001 3
4 489997
490001 4
5 489996
490001 5
6 489995
490001 6
7 489994
490001 7
8 489993
490001 8
9 489992
490001 9
10 489991
490001 10
11 489990
490001 11
12 489989
490001 12
13 489988
490001 13
14 489987
490001 14
15 489986
4900...

output:

989001
1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35
37
39
41
43
45
47
49
51
53
55
57
59
61
63
65
67
69
71
73
75
77
79
81
83
85
87
89
91
93
95
97
99
101
103
105
107
109
111
113
115
117
119
121
123
125
127
129
131
133
135
137
139
141
143
145
147
149
151
153
155
157
159
161
163
165
167
169
171
173
...

result:

ok answer: 989001, maximum: 989001

Test #49:

score: 0
Accepted
time: 504ms
memory: 282268kb

input:

2000000 2000000 1996001
14736 484265
953815 543188
350019 148982
499001 304526
897544 499001
181207 317794
499001 444963
623433 499001
854189 642814
871771 499001
499001 476093
561337 499001
499001 306252
192341 306660
340717 158284
207606 291395
307398 191603
438969 60032
977627 499001
694717 80228...

output:

998001
1
2
3
6
9
14
15
16
17
18
20
21
22
23
24
28
29
31
32
35
36
39
41
43
46
47
48
49
50
53
54
57
58
59
60
61
64
68
69
73
75
77
78
79
80
87
89
91
92
93
94
96
98
102
105
106
110
112
113
115
118
119
124
126
128
130
131
132
134
137
138
139
140
141
142
144
145
147
148
149
151
153
154
159
160
162
163
166...

result:

ok answer: 998001, maximum: 998001

Test #50:

score: 0
Accepted
time: 818ms
memory: 281280kb

input:

2000000 2000000 1999999
268787 212137
905395 946062
578271 1714792
1614896 1709280
854272 878881
905395 1293382
905395 1175387
905395 459499
1747988 83010
1388833 1857081
955129 615008
146195 1709280
905395 795775
513349 906379
847560 1709280
1298422 1709280
573001 1836920
905395 1629231
1272015 197...

output:

1000000
1
3
5
9
10
11
14
17
19
23
24
25
26
28
29
31
33
34
35
36
38
40
44
54
56
58
59
62
66
67
69
70
71
73
74
75
77
79
81
82
85
89
90
93
96
97
99
101
105
106
107
108
109
111
112
116
118
119
121
123
124
127
133
142
145
147
149
150
151
152
159
164
165
166
167
169
170
174
176
177
179
182
183
186
187
188...

result:

ok answer: 1000000, maximum: 1000000

Test #51:

score: 0
Accepted
time: 3238ms
memory: 280676kb

input:

2000000 2000000 1999992
1 333333
333334 1
1 67693
2 333332
333334 2
2 241546
3 333331
333334 3
3 293203
4 333330
333334 4
4 79783
5 333329
333334 5
5 282986
6 333328
333334 6
6 106346
7 333327
333334 7
7 256497
8 333326
333334 8
8 119905
9 333325
333334 9
9 254844
10 333324
333334 10
10 209942
11 33...

output:

665475
1
4
7
10
15
18
19
22
25
28
31
34
37
40
43
46
49
52
57
58
61
64
67
70
73
76
79
82
85
88
91
94
97
100
103
106
109
112
115
118
121
124
127
130
133
136
139
142
145
148
151
154
159
160
163
166
169
172
175
178
181
184
187
190
193
196
199
202
205
208
211
214
217
220
223
226
229
232
235
238
241
244
2...

result:

ok answer: 665475, maximum: 666667

Test #52:

score: 0
Accepted
time: 3349ms
memory: 279480kb

input:

2000000 2000000 1999995
434184 430351
85401 119908
233334 45603
286245 613757
488439 233334
238416 661586
320615 579387
135012 98322
655583 406691
54300 100591
511235 233334
349357 233334
582778 233334
585943 394823
437833 542529
117171 116163
657733 233334
233334 210358
226095 7239
416103 525868
10...

output:

665580
4
6
7
8
16
19
25
26
34
38
39
41
43
44
46
47
50
51
53
56
58
60
70
75
78
81
83
84
92
95
96
97
103
104
105
106
108
112
114
116
118
122
124
127
134
136
141
145
147
153
158
160
161
162
163
164
168
169
174
178
180
181
192
194
196
197
203
205
208
217
218
220
229
232
233
238
242
243
249
251
254
259
2...

result:

ok answer: 665580, maximum: 666667

Test #53:

score: 0
Accepted
time: 3438ms
memory: 280760kb

input:

2000000 2000000 1999997
99936 878006
132599 1532680
808157 573164
99936 1419983
99936 1537850
1848392 1157400
137701 902241
1274770 1105380
99936 102556
792921 1472686
1884966 198885
1687958 1098615
73371 1581777
253000 548850
74925 1185404
1693642 1927029
1534302 837664
796187 910953
99936 236818
1...

output:

663821
10
13
14
16
20
22
23
25
31
33
35
38
41
44
46
49
50
51
52
53
56
57
58
60
72
73
74
76
77
81
89
93
99
100
101
104
111
112
115
117
118
131
132
137
138
140
142
145
148
149
150
152
154
158
163
165
169
171
173
178
181
184
194
198
199
200
202
212
214
215
216
226
227
232
235
236
237
240
242
246
247
25...

result:

ok answer: 663821, maximum: 666667

Test #54:

score: 0
Accepted
time: 3431ms
memory: 283264kb

input:

2000000 2000000 1999999
889649 520969
523056 1286405
1496086 520969
1306343 520969
905937 1014591
1966446 541194
994929 1903865
729217 52620
79941 863746
1966446 568167
1715964 172015
1966446 380997
566912 1559754
268280 188433
568588 63281
1966446 1432646
1926617 637303
1966446 992205
1992855 42917...

output:

865047
5
8
9
11
14
17
23
24
27
28
29
30
32
33
39
41
43
45
46
49
50
59
63
66
70
71
79
80
81
84
85
87
89
90
94
95
101
102
111
113
115
117
119
123
127
129
130
132
133
136
137
138
140
143
148
153
154
155
157
158
159
163
166
169
172
173
177
179
181
182
187
188
193
202
204
207
209
211
214
223
225
226
227
...

result:

ok answer: 865047, maximum: 866667

Test #55:

score: 0
Accepted
time: 508ms
memory: 290848kb

input:

2000000 2000000 1999996
1000001 1000002
1000000 1000001
999999 999998
1000000 999999
1000003 1000004
1000002 1000003
999997 999996
999998 999997
1000005 1000006
1000004 1000005
999995 999994
999996 999995
1000007 1000008
1000006 1000007
999993 999992
999994 999993
1000009 1000010
1000008 1000009
999...

output:

1999995
1
2
3
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
10...

result:

ok answer: 1999995, maximum: 1999995

Test #56:

score: 0
Accepted
time: 1659ms
memory: 174552kb

input:

200000 200000 2000000
664 160724
29731 148042
89719 133217
96668 12241
74180 45431
80359 80359
81360 183670
70023 129871
29348 129404
80903 76108
83946 20731
20513 854
62313 199982
75818 72015
848 120468
52461 121850
28584 2960
29997 157192
5871 138992
50476 50476
63681 7511
74265 141991
37110 18983...

output:

200000
42
45
48
60
76
86
103
106
107
123
129
148
179
193
204
209
210
218
224
230
232
264
281
286
299
303
304
306
310
322
329
338
347
382
383
398
410
431
472
484
487
509
522
544
576
613
616
618
619
625
629
630
650
654
668
682
688
700
708
717
727
732
749
765
806
809
810
819
839
845
856
872
880
890
908...

result:

ok answer: 200000, maximum: 200000

Test #57:

score: 0
Accepted
time: 1717ms
memory: 174736kb

input:

200000 200000 2000000
78113 189591
135248 140966
13931 85453
7945 90406
120041 142669
124018 134787
147034 85469
98588 11461
112366 20587
51999 86074
175326 18428
185557 52954
15782 89330
28609 49472
191098 61077
114813 186608
107339 61746
157614 161856
13633 92037
144083 66351
102406 185761
107676 ...

output:

200000
35
48
60
76
86
87
106
107
119
123
173
179
193
204
210
212
218
286
303
304
306
314
322
327
338
347
382
398
410
433
484
487
510
517
521
522
544
576
581
587
613
616
618
625
629
630
668
700
704
708
717
722
727
732
765
771
782
809
810
819
826
828
832
845
856
858
872
890
900
904
910
920
921
935
936...

result:

ok answer: 200000, maximum: 200000

Test #58:

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

input:

19 19 56
5 19
9 19
2 15
9 17
15 2
4 11
2 6
18 19
16 19
10 4
9 8
12 8
9 13
3 9
14 10
8 5
3 6
6 19
7 12
6 12
18 11
16 15
5 13
3 18
11 17
7 6
8 1
16 2
18 6
9 3
7 18
5 6
1 14
7 11
2 9
2 11
9 15
10 5
14 7
2 19
3 8
1 6
3 11
12 7
5 8
6 15
2 1
10 11
4 6
9 12
5 14
17 15
1 10
9 4
19 10
8 13

output:

18
5
6
9
10
12
14
16
20
23
25
29
30
31
33
39
47
52
55

result:

ok answer: 18, maximum: 18

Test #59:

score: 0
Accepted
time: 6ms
memory: 91896kb

input:

18 15 57
1 11
5 11
17 2
7 8
4 2
3 13
4 5
2 11
3 6
7 12
1 8
5 15
5 10
16 1
13 9
15 7
4 15
11 10
15 15
2 8
5 7
1 3
8 15
6 15
13 4
9 9
4 3
12 9
16 2
17 6
4 12
8 4
16 10
7 9
14 1
4 11
10 12
3 14
16 5
5 12
13 15
5 4
1 4
13 8
18 9
11 15
15 13
5 6
1 1
4 8
3 9
7 5
10 10
12 4
5 8
3 4
3 8

output:

15
18
20
21
22
23
25
29
30
35
36
37
38
45
47
52

result:

ok answer: 15, maximum: 15

Test #60:

score: 0
Accepted
time: 1496ms
memory: 208924kb

input:

678566 678566 1999984
2 9
21 28
40 47
59 66
78 85
97 104
116 123
135 142
154 161
173 180
192 199
211 218
230 237
249 256
268 275
287 294
306 313
325 332
344 351
363 370
382 389
401 408
420 427
439 446
458 465
477 484
496 503
515 522
534 541
553 560
572 579
591 598
610 617
629 636
648 655
667 674
686...

output:

642852
35715
35716
35717
35718
35719
35720
35721
35722
35723
35724
35725
35726
35727
35728
35729
35730
35731
35732
35733
35734
35735
35736
35737
35738
35739
35740
35741
35742
35743
35744
35745
35746
35747
35748
35749
35750
35751
35752
35753
35754
35755
35756
35757
35758
35759
35760
35761
35762
35763...

result:

ok answer: 642852, maximum: 642852

Test #61:

score: 0
Accepted
time: 3275ms
memory: 174552kb

input:

200000 200000 2000000
69876 139185
62524 62525
138 133262
71806 186817
33732 168283
95489 99486
106518 179682
172716 107457
19216 58015
99845 73717
42148 139724
168868 168869
97919 20416
87128 1949
30243 30244
75600 151450
35580 76098
104714 133433
89087 155081
129591 132925
62284 58630
156482 15249...

output:

199999
2
38
40
41
43
52
54
59
61
64
70
80
84
91
97
119
125
140
144
148
150
152
160
164
167
170
175
187
191
193
203
204
206
233
242
254
259
303
304
312
313
327
345
351
379
410
430
453
457
463
473
498
518
526
528
532
542
558
567
575
584
589
597
643
650
657
732
736
737
741
756
773
777
778
784
800
827
8...

result:

ok answer: 199999, maximum: 199999

Test #62:

score: 0
Accepted
time: 1234ms
memory: 171772kb

input:

150000 150000 2000000
54330 43360
16319 88652
141294 26736
20468 113762
97646 145993
60941 104416
129709 105019
66588 68832
142233 2395
108417 104322
6989 77878
88615 37170
143108 87699
61046 70285
57071 89523
51727 37170
9324 127
92556 41325
130418 139947
64056 139176
132912 7652
97699 100501
27494...

output:

150000
19
35
46
60
79
83
114
118
129
174
185
204
224
227
234
242
246
254
263
286
300
303
309
327
335
340
350
360
409
421
437
446
449
457
469
521
540
549
550
568
582
596
600
613
628
643
646
661
673
675
699
730
737
744
750
762
773
776
798
813
823
828
845
848
859
862
866
893
944
960
989
1011
1013
1019
...

result:

ok answer: 150000, maximum: 150000

Test #63:

score: 0
Accepted
time: 1054ms
memory: 168804kb

input:

100000 100000 2000000
49929 65074
29149 97704
24293 81423
66419 49097
11433 84252
92840 60952
62698 90526
88909 86548
17320 20088
51288 89806
96298 83831
38740 34975
44261 80408
29420 71018
58482 68503
52534 60006
58264 78391
56087 93185
82812 85036
8031 14160
66351 20760
14687 96078
15299 90962
518...

output:

100000
22
40
42
51
91
97
140
141
148
160
208
220
250
257
304
336
350
374
400
438
466
469
476
479
524
534
535
556
577
584
618
652
696
699
719
728
776
877
908
923
939
966
982
998
1030
1051
1054
1055
1097
1101
1114
1128
1146
1153
1166
1211
1214
1257
1261
1269
1278
1293
1296
1299
1331
1343
1416
1430
144...

result:

ok answer: 100000, maximum: 100000

Test #64:

score: 0
Accepted
time: 1176ms
memory: 172380kb

input:

170000 170000 2000000
3612 9795
147435 143171
69805 6608
61910 137634
126397 3230
26553 86436
131227 26454
121363 88860
38380 153427
137943 57048
131806 10483
94826 52628
161151 15843
9778 152697
134661 39645
90985 3918
133310 61463
53083 17459
166446 43454
5274 47145
12452 26837
38319 22897
21654 3...

output:

170000
2
18
22
26
36
40
42
44
56
60
62
83
95
101
107
129
138
148
152
163
178
185
209
219
241
242
257
263
274
277
321
341
342
348
360
374
382
387
400
407
422
432
445
449
480
498
515
521
522
526
528
549
579
593
596
604
611
621
646
663
673
674
675
688
737
744
745
749
770
776
790
800
824
839
846
855
873...

result:

ok answer: 170000, maximum: 170000

Test #65:

score: 0
Accepted
time: 3309ms
memory: 180300kb

input:

300000 300000 2000000
105039 159953
139571 260965
123457 12072
17324 259747
138608 110296
66462 272340
110874 210438
122930 567
110889 187260
121538 250086
46088 46088
241860 241860
26309 180815
214266 214266
12616 253964
96698 176066
141876 141876
16967 250287
85301 158549
2708 241153
8648 225106
3...

output:

299766
11
12
14
17
35
38
39
43
56
75
77
87
98
113
115
120
128
134
135
152
164
165
188
197
215
219
239
244
252
264
265
268
273
275
291
295
298
330
331
339
345
348
361
364
368
373
375
384
385
419
427
430
431
440
441
443
446
459
478
479
489
504
505
508
509
527
533
536
545
550
556
559
566
575
577
587
59...

result:

ok answer: 299766, maximum: 300000

Test #66:

score: 0
Accepted
time: 3344ms
memory: 175632kb

input:

250000 250000 2000000
27634 140210
64795 131118
90767 223433
53039 125810
13117 174409
50704 184798
97142 128269
124910 141738
7859 187326
148 117705
43722 145917
79011 152539
67052 44360
55495 46271
37540 172469
106827 175922
124820 124820
119888 78477
89586 71525
98812 210351
12073 12073
58746 118...

output:

249999
17
19
24
26
32
37
40
54
60
73
79
95
99
100
103
121
137
146
149
160
176
178
193
194
201
204
210
216
218
219
220
226
239
248
259
263
265
276
299
322
325
332
333
350
353
354
359
365
379
409
420
424
447
449
451
452
476
485
488
490
502
504
517
528
529
544
545
549
552
553
560
564
572
573
592
597
59...

result:

ok answer: 249999, maximum: 250000

Test #67:

score: 0
Accepted
time: 1021ms
memory: 170888kb

input:

150000 150000 2000000
72620 63166
60504 112442
108921 108921
29772 43296
68163 7790
21709 4273
56314 136135
20691 50652
16581 140984
58236 73716
51216 16671
69149 37016
65297 33957
103215 103215
74270 104198
44645 108573
23166 89329
25025 61044
19899 13984
42237 116930
27561 42622
9294 124923
28200 ...

output:

150000
3
14
41
42
53
78
79
82
103
107
111
116
123
129
134
140
163
178
195
206
236
245
254
257
263
273
279
327
367
402
408
414
443
482
489
507
511
515
520
521
541
546
553
581
587
605
643
644
648
652
662
678
680
695
707
727
730
739
770
800
801
810
811
820
823
828
855
859
862
864
866
872
879
885
907
92...

result:

ok answer: 150000, maximum: 150000

Test #68:

score: 0
Accepted
time: 3392ms
memory: 180564kb

input:

300000 300000 2000000
62650 298300
32903 221473
148069 44049
44572 26768
236134 221925
218630 246970
299097 142733
128764 279567
255792 280789
200357 124110
161834 172221
160384 136502
195281 234298
84582 27950
226733 5498
136989 132152
54414 16936
265690 73937
261962 2088
177657 40267
140454 41167
...

output:

299674
11
12
14
17
35
38
39
43
56
75
77
87
98
113
115
120
128
134
135
152
164
165
188
197
215
219
239
244
252
264
265
268
275
291
295
331
339
345
348
351
361
364
368
373
375
384
385
392
419
427
430
431
440
441
443
446
459
478
489
504
505
508
509
527
533
536
545
550
556
559
566
575
577
587
590
595
64...

result:

ok answer: 299674, maximum: 300000

Test #69:

score: 0
Accepted
time: 3377ms
memory: 176904kb

input:

250000 250000 2000000
42479 78880
229459 199048
215225 39015
67503 87209
44206 177384
181335 32120
218106 232029
131164 22796
37859 147919
118814 39019
18616 29193
56610 107857
234124 125147
192155 239675
61943 77090
27213 222986
91948 178876
16128 160637
201088 72175
125889 246664
203146 93005
4409...

output:

249999
21
24
26
32
40
56
73
75
79
95
99
100
103
113
121
129
137
146
149
160
170
174
176
178
193
201
216
218
219
220
221
223
226
248
257
259
263
265
276
299
304
322
325
332
333
349
350
353
354
359
365
370
379
420
423
424
451
452
470
476
481
485
488
490
502
517
528
529
545
549
552
553
556
558
560
564
...

result:

ok answer: 249999, maximum: 250000

Test #70:

score: 0
Accepted
time: 1316ms
memory: 170896kb

input:

150000 150000 2000000
50295 49713
56629 139465
36117 134593
5619 102228
80472 1462
95204 127674
1068 7827
51488 105256
95178 49920
119485 149320
23548 42551
50754 103530
75573 125223
100703 122055
124159 49080
76472 40393
68125 129299
42342 136831
132673 144177
84740 44446
93983 5263
135511 101001
8...

output:

150000
3
14
26
42
53
82
103
129
140
163
178
185
193
206
236
245
254
269
279
327
333
346
349
360
361
367
377
383
408
414
443
444
472
482
489
507
511
515
520
521
532
533
546
581
596
605
644
648
652
662
673
678
680
707
719
727
728
730
739
770
781
788
810
811
820
855
859
864
872
874
879
885
904
924
935
...

result:

ok answer: 150000, maximum: 150000

Test #71:

score: 0
Accepted
time: 3489ms
memory: 188568kb

input:

400000 400000 2000000
321215 315599
86143 221204
352388 187875
257057 180810
328703 309356
16156 79952
233287 383469
186330 235642
319570 61164
346523 161292
55301 225868
2879 20470
104317 87601
180410 121340
133967 159959
348782 315741
122573 274655
120564 187129
173692 27065
88012 223481
387616 11...

output:

399758
2
11
36
37
40
49
54
65
75
78
79
84
85
89
93
94
95
104
108
113
118
126
129
135
138
147
148
152
170
183
187
212
214
215
217
225
232
245
246
250
253
254
259
263
264
265
269
276
280
286
287
289
299
303
305
307
316
325
327
333
334
335
351
366
369
383
386
391
393
400
407
409
410
414
420
427
436
442...

result:

ok answer: 399758, maximum: 399999

Test #72:

score: 0
Accepted
time: 3485ms
memory: 192204kb

input:

500000 500000 2000000
41258 153561
273035 392661
397020 224200
58608 488748
297485 331670
346512 161259
260630 322105
27539 336545
463787 370096
99457 441303
498391 439092
87501 228594
290136 149064
113483 4060
362030 219228
390362 358525
31241 457801
137393 40805
17584 133295
196052 301094
401557 1...

output:

498980
1
2
3
10
17
21
23
25
32
33
36
37
40
43
59
60
61
71
75
76
78
84
87
89
91
103
107
110
114
120
122
134
141
146
151
155
157
164
168
172
173
181
182
183
185
193
200
202
208
214
217
224
225
227
232
235
240
242
243
247
256
261
262
263
269
271
275
276
277
282
284
286
295
301
302
303
306
309
318
320
3...

result:

ok answer: 498980, maximum: 499999

Test #73:

score: 0
Accepted
time: 3337ms
memory: 188784kb

input:

400000 400000 2000000
24411 11654
148356 10647
227740 5879
386 391268
257182 171
305545 121948
254087 275542
25015 358236
249767 9645
195114 87802
169705 376325
124126 126282
107814 30391
80630 94487
363646 11171
333939 69350
32996 239172
12446 102037
12154 287491
48965 380418
271749 80432
35829 284...

output:

399786
1
2
5
6
13
14
26
30
35
40
41
46
49
59
63
71
74
76
80
82
85
86
93
97
107
132
134
139
140
141
145
149
152
160
167
170
172
174
175
177
191
192
199
209
214
217
231
234
237
239
241
246
247
254
258
261
262
263
265
269
274
276
283
287
299
300
301
303
314
315
318
326
328
329
334
335
339
346
348
350
3...

result:

ok answer: 399786, maximum: 399999

Test #74:

score: 0
Accepted
time: 3366ms
memory: 193944kb

input:

500000 500000 2000000
330811 376879
172454 450741
114896 107867
402163 434806
182433 482459
398350 174732
496493 365171
259063 10910
25942 383521
217410 99230
51323 242993
272491 473326
102357 14366
462674 22816
104426 465142
197666 392939
437531 373348
232972 88117
93026 466729
208134 414081
495308...

output:

498584
4
5
9
13
16
19
23
25
27
37
39
40
44
46
48
49
53
54
66
70
78
79
82
83
85
87
94
95
101
114
121
123
124
127
128
131
132
138
139
140
151
152
160
167
178
179
185
189
194
204
205
209
210
214
219
223
224
226
228
229
231
232
238
243
245
247
248
249
252
253
256
259
263
275
277
278
280
286
289
292
296
...

result:

ok answer: 498584, maximum: 499999

Test #75:

score: 0
Accepted
time: 3266ms
memory: 192680kb

input:

500000 500000 2000000
322807 410913
452232 241894
481008 454652
260794 213674
459518 290982
479472 264462
27434 165765
358893 217733
423071 496151
100484 202619
235325 285732
72905 296158
15183 71591
100768 166531
427812 493809
159311 497845
7747 178375
95452 135039
450314 363747
17199 456516
119084...

output:

498852
2
4
9
15
17
20
24
27
37
40
46
48
49
51
60
62
64
67
75
76
82
86
89
94
96
97
102
103
104
107
108
109
111
114
118
119
128
131
132
134
144
148
152
157
160
163
167
171
172
179
182
183
185
186
187
189
191
199
204
210
214
221
222
235
237
239
241
242
243
250
253
263
270
271
276
277
291
293
294
295
29...

result:

ok answer: 498852, maximum: 499999

Test #76:

score: 0
Accepted
time: 2175ms
memory: 167236kb

input:

100000 100000 2000000
86851 32197
68370 43547
68302 96976
78092 86171
70780 80060
33051 59116
41988 28246
70392 28796
94241 66628
35002 42626
76776 43819
18820 23892
34568 2129
31551 47980
82210 28398
40386 93071
76591 10891
32718 90249
31724 52852
46617 3559
2880 50447
66185 56127
12402 10349
77779...

output:

99999
53
97
145
150
194
204
229
285
309
316
355
361
379
403
409
446
466
469
511
530
581
606
673
682
688
721
730
731
826
843
899
913
923
943
951
1013
1038
1054
1072
1082
1084
1110
1116
1161
1167
1178
1185
1199
1219
1269
1292
1319
1334
1350
1351
1361
1362
1370
1380
1396
1408
1422
1432
1449
1467
1511
1...

result:

ok answer: 99999, maximum: 99999
English 繁體中文 简体中文

Server Time: 2024-12-04 07:33:35 | OpenSource Project