QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#402433#1454. Um nik's AlgorithmmonstersqwqAC ✓3788ms441680kbC++143.7kb2024-04-30 15:57:432024-04-30 15:57:47

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 110728kb

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: 16ms
memory: 110488kb

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: 8ms
memory: 111460kb

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
3
76
91
153
155
168
171
173
233
234
297
398
401
414
428
504
515
583
603
677
697
791
936
954
972
978
987
993
1009
1031
1056
1085
1197
1278
1280
1313
1331
1337
1350
1504
1516
1576
1590
1606
1665
1690
1703
1759
1768
1788
1794
1836
1894
1971
1977
1980
2014
2031
2042
2053
2069
2099
2118
2122
2132
21...

result:

ok answer: 1000, maximum: 1000

Test #4:

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

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
116
150

result:

ok answer: 2, maximum: 2

Test #5:

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

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
25
31
33
34
37
41
42
43
44
45
46
49
50
52
55
58
60
62
63
66
67
70
74
76
78
80
84
85
86
88
89
90
92
94
95
96
97
100
103
107
111
113
114
117
119
120
121
122
125
129
130
131
143
148
149
150
151
154
155
157
160
161
162
163
165
166
167
168
169
173
175
178
179
192
195
196
19...

result:

ok answer: 540, maximum: 540

Test #6:

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

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
17
18
41
46
54
55
60
65
68
72
75
81
91
94
104
152
168
182
187
202
216
222
244
247
252
270
282
303
307
313
315
319
320
321
323
341
366
368
372
375
392
401
408
411
418
427
446
456
458
463
479
488
490
500
513
542
549
567
570
575
587
596
616
620
635
638
645
657
671
674
679
681
683
695
719
721
727
...

result:

ok answer: 944, maximum: 944

Test #7:

score: 0
Accepted
time: 3263ms
memory: 355160kb

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
6
7
8
10
11
12
15
18
23
26
31
34
35
36
38
39
40
41
42
44
45
47
51
55
56
61
62
63
66
67
68
71
74
78
80
84
86
88
89
92
93
94
96
97
98
103
104
105
107
111
113
114
116
117
118
119
120
123
125
126
128
129
131
132
135
138
140
141
143
150
155
157
159
160
163
164
167
168
169
172
173
175
176
178
18...

result:

ok answer: 1088264, maximum: 1088264

Test #8:

score: 0
Accepted
time: 3449ms
memory: 355772kb

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:

1088048
2
3
8
9
14
15
17
20
22
24
25
29
30
34
38
42
43
46
47
48
50
51
56
61
62
64
70
71
72
73
74
75
77
80
84
87
89
91
92
93
95
100
105
108
114
115
119
120
122
123
128
130
131
132
134
139
140
142
148
149
150
151
152
153
155
159
163
165
166
167
168
171
172
176
177
180
184
190
197
200
203
206
211
214
2...

result:

ok answer: 1088048, maximum: 1088048

Test #9:

score: 0
Accepted
time: 3370ms
memory: 355548kb

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
5
12
14
15
24
32
33
34
37
39
40
41
44
45
46
49
50
51
52
56
58
61
65
66
71
74
79
80
81
83
84
85
87
88
91
95
96
99
100
103
105
106
107
109
111
114
115
116
117
119
120
124
125
127
128
129
130
132
134
136
138
140
142
145
146
152
153
154
157
158
164
169
170
174
175
177
179
181
182
183
191
193
2...

result:

ok answer: 1087919, maximum: 1087919

Test #10:

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

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
2
6
8
10
11
12
16
18
19
26
28
31
35
36
37
39
41
45
47
48
49
52
56
58
61
62
64
66
68
69
71
75
76
77
79
80
81
82
92
95
96
97
102
103
104
105
106
107
108
112
113
114
116
117
118
119
121
122
123
124
125
127
131
134
138
139
140
142
143
144
145
148
150
152
154
157
158
159
162
166
167
169
171
176
1...

result:

ok answer: 1088039, maximum: 1088039

Test #11:

score: 0
Accepted
time: 3393ms
memory: 356668kb

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
13
14
15
17
19
20
21
25
26
30
31
34
37
38
41
42
43
45
47
53
54
56
58
59
60
61
63
64
66
67
68
71
72
73
77
81
89
96
98
100
101
103
107
108
110
112
114
117
121
125
126
129
130
132
136
137
142
143
150
154
155
156
158
162
164
168
169
171
172
174
175
177
178
181
183
185
188
190
191
193
1...

result:

ok answer: 1088084, maximum: 1088084

Test #12:

score: 0
Accepted
time: 3480ms
memory: 356348kb

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
3
14
15
17
20
21
22
27
28
29
30
32
33
36
38
39
42
44
46
47
48
51
57
58
59
60
62
64
66
70
74
75
77
81
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
142
143
145
151
153
154
155
156
159
160
161
162
165
169
172
173
178
179
180
183
184
185
187
190
191
...

result:

ok answer: 1087210, maximum: 1087210

Test #13:

score: 0
Accepted
time: 2481ms
memory: 396936kb

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
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
27
28
30
32
33
34
35
36
38
39
41
42
44
46
47
49
50
51
52
53
54
55
56
57
59
60
61
63
65
66
68
69
71
72
73
74
75
79
80
81
82
83
84
85
87
88
89
90
93
95
96
97
100
104
105
106
107
109
110
111
112
113
114
115
116
120
122
125
126
127
128...

result:

ok answer: 1535209, maximum: 1535209

Test #14:

score: 0
Accepted
time: 2129ms
memory: 415808kb

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: 1483ms
memory: 429848kb

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: 1355ms
memory: 441680kb

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: 1147ms
memory: 307644kb

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
130534
133699
202799
228363
397617
584664
782456
915823
1096601
1103323
1129875
1178857
1260088
1292643
1319191
1349480
1506241
1810122
1814857
1999795
1999918
1999925
1999929
1999930
1999933
1999939
1999940
1999959
1999962
1999973
1999982
1999984
1999985
1999988
1999989
1999990
1999992
1999995

result:

ok answer: 38, maximum: 38

Test #18:

score: 0
Accepted
time: 976ms
memory: 331924kb

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
1778614
1999999

result:

ok answer: 2, maximum: 2

Test #19:

score: 0
Accepted
time: 988ms
memory: 334160kb

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
1999999

result:

ok answer: 2, maximum: 2

Test #20:

score: 0
Accepted
time: 1230ms
memory: 313788kb

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
8830
31257
42990
44389
49408
51853
53332
57833
60663
69395
82684
98004
110825
132908
140572
149103
169023
192290
192545
199638
239722
239985
265233
267186
287526
290204
314221
315013
315928
327533
331649
334415
347379
347987
369881
373266
380898
396045
396346
401169
402278
425389
436065
439610
4...

result:

ok answer: 444, maximum: 444

Test #21:

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

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
17
50
83
116
149
182
215
248
281
314
347
380
413
446
479
512
513
530
547
564
581
598
615
632
649
666
683
700
717
734
751
768

result:

ok answer: 32, maximum: 32

Test #22:

score: 0
Accepted
time: 224ms
memory: 186324kb

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
817
2450
4083
5716
7349
8982
10615
12248
13881
15514
17147
18780
20413
22046
23679
25312
26945
28578
30211
31844
33477
35110
36743
38376
40009
41642
43275
44908
46541
48174
49807
51440
53073
54706
56339
57972
59605
61238
62871
64504
66137
67770
69403
71036
72669
74302
75935
77568
79201
80834
82...

result:

ok answer: 1632, maximum: 1632

Test #23:

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

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
64
191
318
445
572
699
826
953
1080
1207
1334
1461
1588
1715
1842
1969
2096
2223
2350
2477
2604
2731
2858
2985
3112
3239
3366
3493
3620
3747
3874
4001
4128
4255
4382
4509
4636
4763
4890
5017
5144
5271
5398
5525
5652
5779
5906
6033
6160
6287
6414
6541
6668
6795
6922
7049
7176
7303
7430
7557
7684
...

result:

ok answer: 189, maximum: 189

Test #24:

score: 0
Accepted
time: 215ms
memory: 192404kb

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
633
1898
3163
4428
5693
6958
8223
9488
10753
12018
13283
14548
15813
17078
18343
19608
20873
22138
23403
24668
25933
27198
28463
29728
30993
32258
33523
34788
36053
37318
38583
39848
41113
42378
43643
44908
46173
47438
48703
49968
51233
52498
53763
55028
56293
57558
58823
60088
61353
62618
6388...

result:

ok answer: 1896, maximum: 1896

Test #25:

score: 0
Accepted
time: 230ms
memory: 220564kb

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
633
1898
3163
4428
5693
6958
8223
9488
10753
12018
13283
14548
15813
17078
18343
19608
20873
22138
23403
24668
25933
27198
28463
29728
30993
32258
33523
34788
36053
37318
38583
39848
41113
42378
43643
44908
46173
47438
48703
49968
51233
52498
53763
55028
56293
57558
58823
60088
61353
62618
6388...

result:

ok answer: 1896, maximum: 1896

Test #26:

score: 0
Accepted
time: 379ms
memory: 262768kb

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
601
1802
3003
4204
5405
6606
7807
9008
10209
11410
12611
13812
15013
16214
17415
18616
19817
21018
22219
23420
24621
25822
27023
28224
29425
30626
31827
33028
34229
35430
36631
37832
39033
40234
41435
42636
43837
45038
46239
47440
48641
49842
51043
52244
53445
54646
55847
57048
58249
59450
60...

result:

ok answer: 183937, maximum: 183937

Test #27:

score: 0
Accepted
time: 1357ms
memory: 262908kb

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
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
95...

result:

ok answer: 184175, maximum: 184175

Test #28:

score: 0
Accepted
time: 459ms
memory: 262900kb

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
696
2185
3196
4589
5911
6730
7821
9098
10542
11827
13003
14333
15263
16368
17412
19121
20099
21337
22643
23962
24865
26141
27534
28238
29533
31076
31957
33143
34488
35909
37049
38174
39491
40415
41983
43088
44010
45118
46503
47521
49144
50220
51111
52786
53812
54759
55844
57171
58653
59403
60...

result:

ok answer: 183975, maximum: 183975

Test #29:

score: 0
Accepted
time: 1839ms
memory: 261304kb

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
324
329
332
350
361
362
370
386
399
401
408
409
420
425
426
439
450
456
469
510
517
519
536
564
572
577
579
587
611
614
621
625
637
645
656
670
690
730
737
743
748
759
762
777
783
786
794
803
845
8...

result:

ok answer: 184156, maximum: 184156

Test #30:

score: 0
Accepted
time: 240ms
memory: 241932kb

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
632
1895
3158
4421
5684
6947
8210
9473
10736
11999
13262
14525
15788
17051
18314
19577
20840
22103
23366
24629
25892
27155
28418
29681
30944
32207
33470
34733
35996
37259
38522
39785
41048
42311
43574
44837
46100
47363
48626
49889
51152
52415
53678
54941
56204
57467
58730
59993
61256
62519
637...

result:

ok answer: 11043, maximum: 11043

Test #31:

score: 0
Accepted
time: 227ms
memory: 238584kb

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
633
1898
3163
4428
5693
6958
8223
9488
10753
12018
13283
14548
15813
17078
18343
19608
20873
22138
23403
24668
25933
27198
28463
29728
30993
32258
33523
34788
36053
37318
38583
39848
41113
42378
43643
44908
46173
47438
48703
49968
51233
52498
53763
55028
56293
57558
58823
60088
61353
62618
6388...

result:

ok answer: 4770, maximum: 4770

Test #32:

score: 0
Accepted
time: 505ms
memory: 253432kb

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
501
1502
2503
3504
4505
5506
6507
7508
8509
9510
10511
11512
12513
13514
14515
15516
16517
17518
18519
19520
20521
21522
22523
23524
24525
25526
26527
27528
28529
29530
30531
31532
32533
33534
34535
35536
36537
37538
38539
39540
40541
41542
42543
43544
44545
45546
46547
47548
48549
49550
50551
...

result:

ok answer: 1505, maximum: 1505

Test #33:

score: 0
Accepted
time: 284ms
memory: 238048kb

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
601
1802
3003
4204
5405
6606
7807
9008
10209
11410
12611
13812
15013
16214
17415
18616
19817
21018
22219
23420
24621
25822
27023
28224
29425
30626
31827
33028
34229
35430
36631
37832
39033
40234
41435
42636
43837
45038
46239
47440
48641
49842
51043
52244
53445
54646
55847
57048
58249
59450
6065...

result:

ok answer: 1804, maximum: 1804

Test #34:

score: 0
Accepted
time: 589ms
memory: 265492kb

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
451
1352
2253
3154
4055
4956
5857
6758
7659
8560
9461
10362
11263
12164
13065
13966
14867
15768
16669
17570
18471
19372
20273
21174
22075
22976
23877
24778
25679
26580
27481
28382
29283
30184
31085
31986
32887
33788
34689
35590
36491
37392
38293
39194
40095
40996
41897
42798
43699
44600
45501
4...

result:

ok answer: 1356, maximum: 1356

Test #35:

score: 0
Accepted
time: 722ms
memory: 297672kb

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
351
1052
1753
2454
3155
3856
4557
5258
5959
6660
7361
8062
8763
9464
10165
10866
11567
12268
12969
13670
14371
15072
15773
16474
17175
17876
18577
19278
19979
20680
21381
22082
22783
23484
24185
24886
25587
26288
26989
27690
28391
29092
29793
30494
31195
31896
32597
33298
33999
34700
35401
3610...

result:

ok answer: 1051, maximum: 1051

Test #36:

score: 0
Accepted
time: 473ms
memory: 263116kb

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
934
2026
2782
4292
5202
6347
7435
8427
9898
10874
12080
12919
14109
15189
16191
17215
18317
19488
20367
21926
22874
23709
24933
25866
27027
28206
29233
30478
31486
32637
33979
34850
35998
37164
38302
39176
40359
41462
42801
43629
44597
45824
47206
48376
49142
50554
51539
52379
53888
54594
55929...

result:

ok answer: 1651, maximum: 1651

Test #37:

score: 0
Accepted
time: 2023ms
memory: 277088kb

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
28384
29848
44487
51578
52513
69922
100030
108217
111543
145620
170803
194433
196655
201422
206853
217012
237639
238780
246160
267563
279520
327105
352136
369055
377965
390549
438255
448217
449371
488427
495558
504009
508584
524590
537780
555432
585903
600819
610612
611198
623268
632175
642398
...

result:

ok answer: 1365, maximum: 1365

Test #38:

score: 0
Accepted
time: 480ms
memory: 253656kb

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
501
1502
2503
3504
4505
5506
6507
7508
8509
9510
10511
11512
12513
13514
14515
15516
16517
17518
18519
19520
20521
21522
22523
23524
24525
25526
26527
27528
28529
29530
30531
31532
32533
33534
34535
35536
36537
37538
38539
39540
40541
41542
42543
43544
44545
45546
46547
47548
48549
49550
50551
...

result:

ok answer: 1515, maximum: 1515

Test #39:

score: 0
Accepted
time: 470ms
memory: 256124kb

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:

2565
806
1612
2418
3224
4030
4836
5642
6448
7254
8060
8866
9672
10478
11284
12090
12896
13702
14508
15314
16120
16926
17732
18538
19344
20150
20956
21762
22568
23374
24180
24986
25792
26598
27404
28210
29016
29822
30628
31434
32240
33046
33852
34658
35464
36270
37076
37882
38688
39494
40300
41106
41...

result:

ok answer: 2565, maximum: 2565

Test #40:

score: 0
Accepted
time: 179ms
memory: 217540kb

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:

2998
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
11000
12000
13000
14000
15000
16000
17000
18000
19000
20000
21000
22000
23000
24000
25000
26000
27000
28000
29000
30000
31000
32000
33000
34000
35000
36000
37000
38000
39000
40000
41000
42000
43000
44000
45000
46000
47000
48000
49000
50000
5100...

result:

ok answer: 2998, maximum: 2998

Test #41:

score: 0
Accepted
time: 3788ms
memory: 232972kb

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:

2880
1235
3003
4142
7575
7610
8679
10069
15100
17117
20166
20996
29533
32065
32754
33411
33801
34104
34440
36289
36944
39391
45135
45742
47059
47637
48384
52168
54575
54730
55700
57821
58857
59760
60681
65045
66675
67542
72448
72506
72686
73450
73704
77187
78400
86211
86793
89086
90098
91636
94674
9...

result:

ok answer: 2880, maximum: 2998

Test #42:

score: 0
Accepted
time: 337ms
memory: 239980kb

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:

2710
901
1802
2703
3604
4505
5406
6307
7208
8109
9010
9911
10812
11713
12614
13515
14416
15317
16218
17119
18020
18921
19822
20723
21624
22525
23426
24327
25228
26129
27030
27931
28832
29733
30634
31535
32436
33337
34238
35139
36040
36941
37842
38743
39644
40545
41446
42347
43248
44149
45050
45951
4...

result:

ok answer: 2710, maximum: 2710

Test #43:

score: 0
Accepted
time: 3576ms
memory: 250536kb

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:

2687
97
316
1281
1416
1767
3499
4963
10785
11958
13711
18571
24036
24418
26870
29028
31280
36130
36366
39015
44846
54043
54549
54597
61243
63802
63968
69063
69500
72696
74291
76612
77182
80199
81162
84298
84497
87792
88457
90084
90604
94091
95048
96821
98205
98412
98509
100437
102671
104129
107976
1...

result:

ok answer: 2687, maximum: 2800

Test #44:

score: 0
Accepted
time: 3751ms
memory: 253480kb

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:

2647
2503
6137
6139
8865
10110
10452
12456
13100
14947
15045
23682
24727
25297
25551
25814
28169
28466
28791
29268
35389
36259
53939
54404
54491
55515
56136
57929
58238
59720
60042
66809
68819
70181
71556
71868
73616
73718
78147
78249
78297
81454
82804
83593
87928
88177
94411
96494
97249
100572
1013...

result:

ok answer: 2647, maximum: 2750

Test #45:

score: 0
Accepted
time: 3779ms
memory: 261300kb

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:

2453
65
222
5331
5382
7655
7704
10951
12850
12955
13147
15542
17609
18393
20317
20844
20955
21739
24760
25605
26714
29680
30732
33586
34765
44607
48454
49668
52210
53672
53860
54774
55817
56476
58447
61171
61348
63671
66780
70766
72937
77092
77516
79229
79895
85763
86232
87189
89190
89831
95691
9606...

result:

ok answer: 2453, maximum: 2530

Test #46:

score: 0
Accepted
time: 474ms
memory: 261168kb

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:

2401
801
1602
2403
3204
4005
4806
5607
6408
7209
8010
8811
9612
10413
11214
12015
12816
13617
14418
15219
16020
16821
17622
18423
19224
20025
20826
21627
22428
23229
24030
24831
25632
26433
27234
28035
28836
29637
30438
31239
32040
32841
33642
34443
35244
36045
36846
37647
38448
39249
40050
40851
41...

result:

ok answer: 2401, maximum: 2401

Test #47:

score: 0
Accepted
time: 902ms
memory: 274264kb

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:

1960
621
1242
1863
2484
3105
3726
4347
4968
5589
6210
6831
7452
8073
8694
9315
9936
10557
11178
11799
12420
13041
13662
14283
14904
15525
16146
16767
17388
18009
18630
19251
19872
20493
21114
21735
22356
22977
23598
24219
24840
25461
26082
26703
27324
27945
28566
29187
29808
30429
31050
31671
32292
...

result:

ok answer: 1960, maximum: 1960

Test #48:

score: 0
Accepted
time: 369ms
memory: 323432kb

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: 1367ms
memory: 326716kb

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: 1524ms
memory: 335444kb

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: 3426ms
memory: 283280kb

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:

665075
1
4
7
10
13
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
132
133
136
139
142
145
148
151
154
159
160
163
166
169
172
175
178
181
184
187
190
195
196
199
202
205
210
211
214
217
220
223
226
229
232
235
238
241
244
2...

result:

ok answer: 665075, maximum: 666667

Test #52:

score: 0
Accepted
time: 3504ms
memory: 282924kb

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:

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

result:

ok answer: 666059, maximum: 666667

Test #53:

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

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:

665708
7
12
13
14
15
16
20
22
23
25
31
33
35
38
41
44
49
50
51
52
53
56
57
58
60
72
73
74
76
77
81
89
93
100
101
104
111
112
117
118
125
126
132
137
138
140
142
145
148
150
152
154
158
163
165
169
171
173
178
181
184
186
198
199
200
202
214
215
216
226
227
232
236
239
240
242
246
247
248
252
260
261...

result:

ok answer: 665708, maximum: 666667

Test #54:

score: 0
Accepted
time: 3619ms
memory: 319560kb

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:

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

result:

ok answer: 864446, maximum: 866667

Test #55:

score: 0
Accepted
time: 574ms
memory: 441376kb

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
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
10...

result:

ok answer: 1999995, maximum: 1999995

Test #56:

score: 0
Accepted
time: 3407ms
memory: 209848kb

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
30
48
76
86
106
107
116
123
179
190
210
218
264
286
291
304
310
322
338
347
380
382
398
410
484
487
534
544
576
613
616
625
630
633
668
708
717
727
732
765
774
809
810
819
845
856
858
872
910
920
936
947
949
958
962
980
1003
1032
1037
1043
1119
1129
1135
1147
1169
1183
1210
1215
1219
1233
123...

result:

ok answer: 200000, maximum: 200000

Test #57:

score: 0
Accepted
time: 3333ms
memory: 209456kb

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
48
67
76
86
106
107
123
179
210
213
218
259
286
304
322
338
347
382
398
410
484
487
521
544
576
579
581
613
616
625
630
668
708
717
727
732
765
805
809
810
819
833
845
856
872
890
910
920
936
947
949
958
962
980
1002
1003
1032
1037
1119
1129
1135
1169
1183
1199
1210
1215
1219
1237
1238
1266
1...

result:

ok answer: 200000, maximum: 200000

Test #58:

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

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: 12ms
memory: 101892kb

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
5
8
10
21
22
30
35
38
39
44
45
46
47
53
54

result:

ok answer: 15, maximum: 15

Test #60:

score: 0
Accepted
time: 558ms
memory: 259292kb

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: 3552ms
memory: 207300kb

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:

199866
60
70
80
125
187
208
259
326
356
361
640
727
758
778
827
830
876
903
905
915
950
1075
1122
1157
1163
1169
1209
1232
1442
1493
1530
1613
1630
1641
1694
1720
1729
1815
1919
1920
1969
1977
2007
2031
2034
2039
2079
2108
2155
2185
2231
2301
2330
2341
2365
2389
2447
2467
2474
2500
2521
2563
2610
26...

result:

ok answer: 199866, maximum: 199999

Test #62:

score: 0
Accepted
time: 2349ms
memory: 203960kb

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
208
224
295
312
340
529
530
543
572
625
672
675
711
724
744
866
982
1036
1185
1194
1362
1457
1468
1629
1673
1777
1845
1910
1928
1947
1968
2018
2049
2200
2204
2786
2859
3053
3066
3149
3181
3279
3310
3325
3380
3454
3594
3595
3631
3662
3859
3863
3922
4003
4290
4421
4695
4699
4709
4717
4813
4925
...

result:

ok answer: 150000, maximum: 150000

Test #63:

score: 0
Accepted
time: 2292ms
memory: 196860kb

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
25
64
73
324
348
375
489
535
564
696
939
966
972
1125
1139
1156
1237
1296
1461
1466
1792
1818
1900
1939
1985
2015
2124
2191
2456
2488
2510
2740
2826
2892
2939
3204
3226
3498
3753
3782
3810
3824
3968
4164
4196
4659
4888
4921
5151
5180
5245
5253
5390
5408
5555
5652
5758
5833
5891
5995
6036
6129...

result:

ok answer: 100000, maximum: 100000

Test #64:

score: 0
Accepted
time: 2467ms
memory: 211144kb

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
36
81
102
179
219
221
300
445
579
605
862
970
1013
1068
1083
1086
1091
1128
1402
1429
1463
1480
1490
1597
2113
2195
2213
2306
2403
2591
2597
2759
2861
2990
2997
2998
3005
3035
3036
3182
3447
3449
3451
3535
3576
3648
3743
3959
3985
3988
4051
4130
4248
4346
4621
4779
4821
4854
4901
4940
4980
51...

result:

ok answer: 170000, maximum: 170000

Test #65:

score: 0
Accepted
time: 3500ms
memory: 224412kb

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:

298832
11
12
14
17
35
38
39
43
56
75
87
98
113
115
120
128
134
135
152
164
165
188
197
215
219
239
244
252
264
268
291
295
322
330
331
339
345
361
364
368
373
375
384
385
419
427
430
431
440
441
443
446
459
478
489
491
504
505
508
509
533
536
545
550
556
559
566
575
577
587
590
595
641
649
654
656
6...

result:

ok answer: 298832, maximum: 300000

Test #66:

score: 0
Accepted
time: 3622ms
memory: 218836kb

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:

249905
24
32
37
52
73
75
95
103
121
137
146
149
176
178
201
216
218
219
220
226
239
248
252
259
265
276
299
325
332
333
341
353
354
357
359
365
369
379
395
402
409
447
451
452
485
488
490
502
504
517
528
529
545
549
560
564
572
573
597
599
615
621
626
666
684
711
720
735
752
764
768
801
806
811
815
...

result:

ok answer: 249905, maximum: 250000

Test #67:

score: 0
Accepted
time: 2581ms
memory: 208324kb

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
42
53
103
178
206
227
236
245
254
279
295
367
414
443
482
507
511
515
520
546
605
613
644
648
662
678
680
707
709
739
758
810
811
820
872
879
924
935
943
946
974
1005
1013
1042
1119
1126
1165
1183
1192
1198
1217
1221
1235
1247
1280
1282
1286
1302
1304
1318
1336
1350
1357
1398
1400
1467
1...

result:

ok answer: 150000, maximum: 150000

Test #68:

score: 0
Accepted
time: 3499ms
memory: 223512kb

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:

298507
11
12
14
17
35
38
39
43
56
75
77
87
113
115
120
128
134
135
152
164
178
188
197
215
219
239
244
252
264
268
273
291
295
298
331
339
345
348
355
357
361
364
368
373
375
384
385
419
427
430
431
440
441
443
446
447
459
478
489
504
505
508
509
533
536
545
550
556
559
566
575
577
587
590
595
605
6...

result:

ok answer: 298507, maximum: 300000

Test #69:

score: 0
Accepted
time: 3464ms
memory: 222556kb

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:

249770
27
32
52
73
95
96
103
121
137
146
149
176
178
201
216
218
219
220
223
226
248
258
259
265
276
299
325
332
333
353
354
359
365
379
405
409
423
433
447
451
452
485
488
490
502
517
528
529
533
544
545
549
560
564
572
573
592
597
599
615
621
626
666
684
711
735
738
752
764
772
801
806
813
816
826...

result:

ok answer: 249770, maximum: 250000

Test #70:

score: 0
Accepted
time: 2554ms
memory: 208576kb

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
42
53
103
178
206
236
245
254
279
367
381
414
443
482
507
511
515
520
546
605
618
644
648
662
678
680
707
739
810
811
820
872
879
924
935
943
946
974
1005
1013
1119
1126
1165
1183
1198
1217
1221
1235
1247
1271
1280
1282
1286
1302
1304
1318
1336
1350
1357
1398
1400
1467
1470
1515
1533
155...

result:

ok answer: 150000, maximum: 150000

Test #71:

score: 0
Accepted
time: 3748ms
memory: 233392kb

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:

397168
2
11
12
32
34
36
38
42
56
61
73
81
83
91
93
95
113
121
125
126
135
157
158
160
174
183
196
198
200
217
225
246
250
254
278
280
283
287
305
314
340
359
365
371
372
375
385
389
399
407
414
423
431
432
433
440
443
453
456
458
481
482
491
492
501
512
513
515
518
530
556
566
576
578
588
590
624
64...

result:

ok answer: 397168, maximum: 399999

Test #72:

score: 0
Accepted
time: 3694ms
memory: 244896kb

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:

495159
10
14
19
20
21
28
32
43
61
64
65
67
75
86
87
93
94
95
113
114
126
135
141
151
155
157
159
168
189
195
201
208
216
218
223
224
225
231
239
242
249
256
258
268
271
277
281
291
297
300
325
328
332
333
340
346
354
355
363
395
398
415
416
421
445
447
457
466
469
470
489
498
500
504
505
507
514
517...

result:

ok answer: 495159, maximum: 499999

Test #73:

score: 0
Accepted
time: 3739ms
memory: 233440kb

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:

399386
2
4
28
73
82
84
86
93
105
107
112
129
130
141
151
153
161
163
170
173
174
184
192
202
212
214
237
239
243
312
318
319
323
328
346
348
350
369
371
375
378
389
395
400
407
416
428
431
437
457
458
510
521
523
527
535
552
575
580
588
600
604
605
609
613
649
651
662
681
685
705
713
726
747
758
763...

result:

ok answer: 399386, maximum: 399999

Test #74:

score: 0
Accepted
time: 3537ms
memory: 244972kb

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:

494030
1
17
25
65
66
67
74
76
118
121
123
129
132
133
138
160
162
171
173
185
190
194
205
221
233
239
242
248
284
286
291
294
295
299
312
314
333
334
371
372
383
402
423
424
436
451
454
461
462
479
483
488
489
490
505
506
514
519
526
534
542
543
547
548
575
595
604
612
614
616
639
640
642
643
644
65...

result:

ok answer: 494030, maximum: 499999

Test #75:

score: 0
Accepted
time: 3591ms
memory: 246052kb

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:

495503
2
4
9
22
24
36
37
46
48
57
59
64
65
68
82
85
89
102
104
106
109
111
112
114
115
124
135
152
163
168
177
190
191
200
203
212
236
239
243
244
253
271
283
292
296
301
302
308
311
320
321
326
329
332
352
366
374
377
388
390
395
400
414
420
421
423
426
429
432
434
441
442
444
445
455
463
468
472
4...

result:

ok answer: 495503, maximum: 499999

Test #76:

score: 0
Accepted
time: 3552ms
memory: 201980kb

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:

99962
69
82
137
277
303
461
533
790
856
1083
1284
1317
1332
1430
1476
1512
1822
1890
1911
2020
2115
2187
2318
2409
2416
2605
2713
2938
2953
3006
3014
3062
3167
3264
3286
3336
3440
3449
3475
3514
3534
3628
3817
3837
4056
4058
4071
4087
4370
4441
4457
4518
4880
4957
5038
5089
5194
5270
5440
5457
5624
...

result:

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

Server Time: 2024-12-03 12:00:50 | OpenSource Project