QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#417104#1454. Um nik's AlgorithmqiuzxAC ✓2490ms290208kbC++203.0kb2024-05-22 14:24:232024-05-22 14:24:25

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 87984kb

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: 11ms
memory: 87136kb

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

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
7
32
44
51
56
75
86
87
98
100
114
116
140
146
149
157
178
185
186
193
202
210
217
226
231
240
250
256
283
289
294
297
312
320
322
324
327
330
331
344
350
359
377
382
398
406
444
449
457
486
487
488
493
500
505
510
526
533
538
543
544
552
555
561
578
584
608
610
624
629
630
639
646
682
688
711...

result:

ok answer: 1000, maximum: 1000

Test #4:

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

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: 88620kb

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
6
7
10
11
17
18
21
22
30
31
33
34
37
41
42
43
44
45
46
48
49
50
52
53
55
58
60
62
63
65
66
67
70
73
74
75
76
78
80
82
84
85
88
89
90
92
93
94
95
96
97
100
103
105
107
108
111
113
114
117
119
120
121
122
125
129
130
132
139
140
143
144
148
150
151
154
155
156
157
160
161
162
163
164
165
166...

result:

ok answer: 540, maximum: 540

Test #6:

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

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
5
15
17
18
25
32
36
37
40
41
46
52
54
55
60
61
64
65
68
70
73
75
78
79
80
81
91
94
96
99
104
105
110
112
118
124
125
126
129
135
140
153
155
156
157
158
160
164
168
169
172
173
174
175
178
179
182
184
186
195
200
202
207
211
212
216
222
225
230
237
244
245
247
252
254
256
257
261
264
266
270
2...

result:

ok answer: 944, maximum: 944

Test #7:

score: 0
Accepted
time: 2462ms
memory: 286800kb

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
4
6
7
8
10
11
12
15
18
23
25
26
29
31
34
35
36
38
39
40
41
42
43
44
45
47
51
55
56
58
61
62
63
65
66
67
68
71
72
74
78
80
81
84
86
88
89
93
94
96
97
98
99
102
103
104
105
107
110
111
113
114
116
117
118
119
120
121
125
126
127
128
129
132
135
136
137
138
140
141
142
143
148
149
150
155
1...

result:

ok answer: 1088264, maximum: 1088264

Test #8:

score: 0
Accepted
time: 2490ms
memory: 286428kb

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
4
8
9
13
14
15
17
20
22
24
25
29
30
34
38
39
42
43
44
46
47
48
50
51
52
55
56
59
62
64
70
71
72
73
74
75
76
77
79
80
84
87
89
91
92
93
95
97
98
100
103
105
108
113
114
115
116
117
119
120
122
123
125
128
130
131
132
134
139
140
142
144
146
148
149
150
151
152
153
155
157
159
163
164
165
...

result:

ok answer: 1088048, maximum: 1088048

Test #9:

score: 0
Accepted
time: 2229ms
memory: 286508kb

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
4
5
12
14
15
19
24
31
32
33
34
35
39
40
41
44
45
46
47
49
50
51
52
56
61
65
66
67
69
71
74
77
79
80
81
83
84
85
87
88
91
95
96
97
99
100
102
103
105
106
107
109
111
114
115
116
117
118
119
120
121
122
124
125
127
128
129
130
132
134
136
137
138
140
142
143
145
146
148
149
152
153
154
156
1...

result:

ok answer: 1087919, maximum: 1087919

Test #10:

score: 0
Accepted
time: 2055ms
memory: 290208kb

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
4
6
8
11
12
16
18
19
24
26
28
31
35
36
37
39
41
45
47
48
49
51
52
56
58
61
62
63
64
66
67
68
69
71
75
76
77
79
80
81
82
92
94
95
96
97
100
102
103
104
105
106
107
108
110
112
113
114
116
117
118
119
120
121
122
123
124
125
127
131
132
133
134
137
138
139
140
142
143
144
148
150
152
153
154...

result:

ok answer: 1088039, maximum: 1088039

Test #11:

score: 0
Accepted
time: 2281ms
memory: 286896kb

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
6
8
9
13
14
15
17
18
19
20
21
22
25
26
30
31
34
36
37
38
40
41
42
43
44
45
47
48
53
54
55
56
58
59
60
61
63
64
66
67
68
71
72
73
77
81
82
89
96
98
100
101
103
105
107
108
110
112
114
116
117
118
121
122
125
126
129
130
132
136
137
141
142
143
148
150
154
155
156
162
164
168
169
171
172...

result:

ok answer: 1088084, maximum: 1088084

Test #12:

score: 0
Accepted
time: 2299ms
memory: 287232kb

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
6
14
16
17
18
20
21
22
24
28
29
30
32
38
39
41
42
44
46
47
48
50
51
52
54
57
58
59
60
62
64
66
70
74
75
76
77
79
81
87
89
90
92
93
94
95
97
98
99
100
103
105
106
107
109
110
111
114
115
116
118
121
123
128
132
133
138
139
142
143
145
146
147
153
154
155
156
158
159
160
161
162
165
169
...

result:

ok answer: 1087210, maximum: 1087210

Test #13:

score: 0
Accepted
time: 1144ms
memory: 288932kb

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
25
27
28
29
30
32
33
34
35
36
38
39
41
42
44
46
47
48
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
98
100
104
105
106
107
109
110
111
112
113
114
115
116
11...

result:

ok answer: 1535209, maximum: 1535209

Test #14:

score: 0
Accepted
time: 774ms
memory: 288860kb

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: 699ms
memory: 288992kb

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: 614ms
memory: 287824kb

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: 347ms
memory: 275732kb

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
13710
130534
133699
202799
228363
231122
282025
368611
387553
397617
547721
584664
647025
782456
787476
870796
915823
956762
967160
969178
1065239
1074670
1096601
1103323
1129875
1178857
1260088
1267431
1280048
1285878
1292643
1313243
1319191
1326614
1810122
1814857
1891081
1913009

result:

ok answer: 38, maximum: 38

Test #18:

score: 0
Accepted
time: 256ms
memory: 278800kb

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

result:

ok answer: 2, maximum: 2

Test #19:

score: 0
Accepted
time: 275ms
memory: 278388kb

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
186331
550532

result:

ok answer: 2, maximum: 2

Test #20:

score: 0
Accepted
time: 394ms
memory: 279156kb

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
4105
8830
13710
14622
29100
31257
31351
36489
42990
44389
47418
49408
51853
53332
54923
57833
60663
69395
74461
77221
82684
96210
98004
104248
110825
129629
132882
132908
138536
140572
144736
148545
149103
154945
158341
159727
169023
174678
174840
178747
186331
191697
192290
192545
199638
213785...

result:

ok answer: 444, maximum: 444

Test #21:

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

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
30
63
93
118
155
178
217
250
284
320
340
373
407
435
472
497
513
535
554
563
581
605
619
640
644
670
674
696
716
735
745
758

result:

ok answer: 32, maximum: 32

Test #22:

score: 0
Accepted
time: 234ms
memory: 161840kb

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
1082
3029
4296
6524
8145
9190
11204
12655
14255
16177
17510
19413
20585
22831
23839
25433
26986
28891
30494
32344
33773
35725
37331
38504
40538
41910
43840
45315
46708
48868
49794
51793
53851
55330
57100
58449
60319
61425
62932
64498
66194
68008
70155
71223
73236
74876
76623
78295
79787
81073
8...

result:

ok answer: 1632, maximum: 1632

Test #23:

score: 0
Accepted
time: 4ms
memory: 92108kb

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
116
212
364
442
592
724
873
992
1088
1200
1339
1494
1589
1745
1875
1972
2121
2263
2357
2517
2640
2747
2864
3011
3109
3225
3372
3520
3593
3747
3863
3976
4119
4229
4379
4514
4603
4759
4907
4986
5166
5256
5417
5496
5659
5739
5870
6013
6146
6274
6399
6507
6625
6784
6918
7052
7165
7250
7410
7558
7644...

result:

ok answer: 189, maximum: 189

Test #24:

score: 0
Accepted
time: 412ms
memory: 160044kb

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
735
2122
3216
4652
6086
7519
8302
10094
11164
12292
13352
14545
16215
17328
18459
20091
21173
22462
23521
24773
26375
27782
28589
30334
31448
32384
34111
35312
36635
37457
39135
40228
41345
42835
44029
45345
46338
47647
48759
50081
51435
52833
54145
55476
56524
57616
58908
60574
61640
62734
643...

result:

ok answer: 1896, maximum: 1896

Test #25:

score: 0
Accepted
time: 575ms
memory: 273268kb

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
735
2122
3216
4652
6086
7519
8302
10094
11164
12292
13352
14545
16215
17328
18459
20091
21173
22462
23521
24773
26375
27782
28589
30334
31448
32384
34111
35312
36635
37457
39135
40228
41345
42835
44029
45345
46338
47647
48759
50081
51435
52833
54145
55476
56524
57616
58908
60574
61640
62734
643...

result:

ok answer: 1896, maximum: 1896

Test #26:

score: 0
Accepted
time: 664ms
memory: 275624kb

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
698
2257
3139
4626
5856
6611
7970
9473
10739
11667
12990
14320
15090
16348
17423
18644
20233
21226
22405
23519
24787
26238
27036
28496
29843
30742
32384
33375
34315
35823
36985
37842
39272
40672
41467
42784
43807
45414
46328
47919
48647
50336
51246
52466
53851
54775
56385
57197
58399
59687
60...

result:

ok answer: 183937, maximum: 183937

Test #27:

score: 0
Accepted
time: 644ms
memory: 277308kb

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: 902ms
memory: 276992kb

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
994
2082
3547
4430
5683
7196
8348
9516
10468
11508
13119
14013
15013
16525
17942
18874
19964
21580
22657
23519
24787
26071
27299
28711
29870
30715
32079
33523
34221
35442
36897
38309
39584
40712
41599
43170
44400
45056
46566
47418
48952
50016
51435
52799
53527
55128
56216
57197
58356
59705
60...

result:

ok answer: 183975, maximum: 183975

Test #29:

score: 0
Accepted
time: 873ms
memory: 273828kb

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
14
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
520
536
564
572
577
579
587
611
614
621
625
627
631
637
645
653
656
670
690
730
737
743
748
759
762
77...

result:

ok answer: 184156, maximum: 184156

Test #30:

score: 0
Accepted
time: 567ms
memory: 273892kb

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
854
2395
3508
4709
5822
7502
8656
9821
11237
12306
13865
15080
16145
17592
18874
19640
21096
22598
23662
25154
26077
27563
28893
30151
31351
32743
33830
35290
36516
37857
38887
39870
41503
42328
43695
45271
46173
47426
49131
50346
51443
52415
54115
55221
56559
57760
59021
60313
61425
62936
639...

result:

ok answer: 11043, maximum: 11043

Test #31:

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

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
958
2233
3227
4805
6150
7266
8547
9943
10988
12157
13745
14897
16411
17261
18746
20216
21202
22703
23855
24773
26461
27782
28723
30046
31435
32672
34111
35312
36437
37611
38748
40208
41176
42377
44085
44927
46338
47835
48868
50081
51459
52750
53851
55360
56524
57571
59300
60466
61425
63176
6409...

result:

ok answer: 4770, maximum: 4770

Test #32:

score: 0
Accepted
time: 528ms
memory: 276204kb

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
682
1575
2918
3883
4928
5737
6726
7990
8922
9906
10538
11701
12603
13955
14754
15557
16677
17693
18644
19978
20559
21720
22703
23805
24753
25578
26770
27630
28891
29633
30742
31620
32597
33776
34541
35518
36762
37757
38768
39568
40919
41599
42842
43678
44564
45722
46788
47656
48699
49592
50863
...

result:

ok answer: 1505, maximum: 1505

Test #33:

score: 0
Accepted
time: 591ms
memory: 273348kb

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
698
2257
3139
4626
5856
6611
7970
9473
10739
11667
12990
14320
15090
16348
17423
18644
20233
21226
22405
23519
24787
26238
27036
28496
29843
30742
32384
33375
34315
35823
36985
37842
39272
40672
41467
42784
43807
45414
46328
47919
48647
50336
51246
52466
53851
54775
56385
57197
58399
59687
6098...

result:

ok answer: 1804, maximum: 1804

Test #34:

score: 0
Accepted
time: 543ms
memory: 276580kb

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
609
1586
2691
3291
4443
5135
6078
6807
8051
8866
9488
10453
11499
12383
13119
14064
15013
16113
16862
17812
18879
19352
20683
21297
22081
23173
24259
24859
26072
26572
27474
28661
29346
30186
31105
32241
32871
34016
35087
35823
36871
37757
38417
39474
40056
41228
41932
42769
43997
44967
45722
4...

result:

ok answer: 1356, maximum: 1356

Test #35:

score: 0
Accepted
time: 442ms
memory: 276552kb

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
423
1087
2038
2764
3302
4041
4608
5490
5998
6876
7533
8284
8920
9732
10391
11171
11667
12339
13218
13717
14435
15193
15828
16772
17317
18110
18819
19273
19963
20662
21537
22081
22847
23747
24429
24859
25796
26502
27299
27897
28686
29277
29887
30512
31233
32079
32665
33290
34230
34949
35397
3634...

result:

ok answer: 1051, maximum: 1051

Test #36:

score: 0
Accepted
time: 710ms
memory: 273716kb

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
1023
1684
3123
4105
5306
6116
7258
8725
9390
10483
12096
12708
14181
15013
16355
17322
18403
19587
20834
21949
22898
24019
24787
26071
27145
28117
29341
30420
31799
32651
34015
35120
36252
37249
38348
39272
40272
41467
42377
43584
45005
45722
46946
48239
48952
50198
51687
52750
53642
54567
5575...

result:

ok answer: 1651, maximum: 1651

Test #37:

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

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
3011
3296
6063
6366
9048
10451
11392
11508
11636
13687
14050
14090
15213
19964
21949
22081
25708
28384
29848
32446
32982
33154
33696
37608
38843
41081
42152
42535
44737
47418
48099
48427
49303
51578
51802
52063
52513
54115
54760
60462
60974
62471
63761
67209
70642
71106
73626
78574
78640
79639
...

result:

ok answer: 1365, maximum: 1365

Test #38:

score: 0
Accepted
time: 594ms
memory: 273464kb

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
682
1575
2918
3883
4928
5737
6726
7990
8922
9906
10538
11701
12603
13955
14754
15557
16677
17693
18644
19978
20559
21720
22703
23805
24753
25578
26770
27630
28891
29633
30742
31620
32597
33776
34541
35518
36762
37757
38768
39568
40919
41599
42842
43678
44564
45722
46788
47656
48699
49592
50863
...

result:

ok answer: 1515, maximum: 1515

Test #39:

score: 0
Accepted
time: 2282ms
memory: 276308kb

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:

2506
48321
49129
49968
50724
51582
52327
53167
53979
54760
55578
56381
57197
57986
58770
59630
60398
61191
61995
62863
63629
64449
65248
66049
66889
67675
68479
69265
70094
70893
71662
72502
73263
74145
74944
75699
76502
77349
78131
78957
79733
80596
81330
82171
82993
83748
84622
85377
86201
87003
8...

result:

ok answer: 2506, maximum: 2565

Test #40:

score: 0
Accepted
time: 2393ms
memory: 274648kb

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:

2934
64975
65991
66991
67963
68985
69967
70999
71983
72953
73927
74944
75966
76974
77975
78953
79966
80923
81986
82983
83992
84945
85927
86951
87936
88916
89999
90937
91953
92991
93942
94916
95982
96993
97987
98966
100000
100976
101967
102946
103940
104993
105982
106992
107910
108905
109998
110990
1...

result:

ok answer: 2934, maximum: 2998

Test #41:

score: 0
Accepted
time: 2456ms
memory: 273416kb

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:

2936
279
1235
2469
3003
4142
4418
6732
7575
7610
8679
9483
10069
11193
12339
12396
14013
14181
15100
15300
17117
17322
18670
19587
19940
20166
20416
20996
22233
22652
22669
24429
25222
26474
29533
30350
31281
31520
32754
33411
33801
34104
34440
34872
35286
36054
36289
38866
42769
42948
42955
44830
4...

result:

ok answer: 2936, maximum: 2998

Test #42:

score: 0
Accepted
time: 2222ms
memory: 275200kb

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:

2643
61241
62113
63044
63910
64809
65764
66621
67526
68445
69373
70222
71106
72065
72953
73833
74730
75631
76502
77483
78340
79238
80111
81063
81981
82888
83749
84648
85579
86471
87385
88247
89161
90091
90975
91859
92704
93678
94601
95446
96376
97277
98168
99095
100009
100872
101715
102704
103527
10...

result:

ok answer: 2643, maximum: 2710

Test #43:

score: 0
Accepted
time: 2472ms
memory: 276088kb

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:

2740
97
316
347
367
1281
1416
2234
2685
2861
3691
4963
6405
7664
7741
8084
8675
8685
9187
10250
10785
11958
12173
13391
13711
14539
14969
15199
15221
15959
16785
18571
20733
21876
21887
24036
24047
24418
26128
26870
28711
29028
30321
30403
30420
31280
31292
31539
32335
33585
35658
36130
36252
36366
...

result:

ok answer: 2740, maximum: 2800

Test #44:

score: 0
Accepted
time: 2455ms
memory: 273868kb

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:

2693
401
520
2503
3400
3551
4519
4572
5017
6137
6139
7033
7426
8865
9061
9338
9926
10452
12190
12456
13100
15013
15045
16450
16622
17616
18403
20153
21606
21669
23243
23556
23682
24727
25297
25551
25672
25814
28169
28216
28466
28791
29268
29607
29749
31263
31915
31929
32553
35125
35389
36088
36259
3...

result:

ok answer: 2693, maximum: 2750

Test #45:

score: 0
Accepted
time: 2268ms
memory: 274620kb

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:

2477
65
222
357
3011
5382
5709
6117
7043
7325
7655
7704
9600
10951
12173
12281
12850
12955
13147
15115
15524
15542
15893
16506
17176
17609
17779
18061
18393
18569
18839
20441
20844
20955
21071
21178
21739
22753
23436
25338
25605
26128
26714
27064
27562
29680
30350
30732
31233
31828
32704
32820
33586...

result:

ok answer: 2477, maximum: 2530

Test #46:

score: 0
Accepted
time: 2231ms
memory: 274960kb

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:

2353
39224
40031
40850
41651
42414
43228
44047
44830
45616
46448
47204
48045
48805
49619
50429
51246
52063
52833
53664
54434
55210
56035
56802
57654
58453
59241
60057
60849
61669
62470
63225
64079
64859
65621
66472
67209
68008
68806
69644
70455
71276
72065
72882
73685
74462
75238
76056
76843
77689
7...

result:

ok answer: 2353, maximum: 2401

Test #47:

score: 0
Accepted
time: 2246ms
memory: 275488kb

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:

1910
31669
32291
32907
33481
34117
34761
35368
35985
36618
37213
37857
38470
39075
39690
40320
40942
41559
42186
42842
43463
44034
44671
45265
45913
46527
47127
47744
48427
48992
49677
50231
50885
51500
52156
52764
53322
53994
54581
55241
55850
56464
57100
57689
58326
58908
59559
60192
60815
61404
6...

result:

ok answer: 1910, maximum: 1960

Test #48:

score: 0
Accepted
time: 374ms
memory: 283204kb

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: 489ms
memory: 284288kb

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: 624ms
memory: 282920kb

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: 2251ms
memory: 283568kb

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:

665942
1
4
7
10
13
16
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
157
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: 665942, maximum: 666667

Test #52:

score: 0
Accepted
time: 2262ms
memory: 279608kb

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:

665890
4
6
7
8
16
19
24
25
26
34
38
39
41
43
44
46
47
50
51
53
56
58
59
60
70
75
78
81
84
91
92
95
96
97
101
103
105
106
108
112
114
116
118
122
124
127
134
136
141
145
147
153
157
158
160
161
162
163
164
168
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: 665890, maximum: 666667

Test #53:

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

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:

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

result:

ok answer: 665143, maximum: 666667

Test #54:

score: 0
Accepted
time: 2320ms
memory: 283156kb

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:

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

result:

ok answer: 864361, maximum: 866667

Test #55:

score: 0
Accepted
time: 515ms
memory: 287840kb

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: 1403ms
memory: 172920kb

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
4
21
25
30
47
48
51
70
76
86
87
105
106
107
116
123
125
129
170
173
179
210
213
214
216
218
235
240
264
268
271
273
286
304
306
322
325
338
347
367
378
382
398
410
415
459
484
487
489
520
544
576
579
590
601
613
616
625
630
643
650
656
668
708
712
717
727
728
732
756
757
763
765
809
810
818
8...

result:

ok answer: 200000, maximum: 200000

Test #57:

score: 0
Accepted
time: 1522ms
memory: 173108kb

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
30
44
47
48
51
76
86
87
106
107
123
153
179
199
205
210
216
217
218
238
240
268
282
286
304
306
319
322
338
347
351
367
371
378
382
389
392
398
410
433
468
484
487
509
544
568
576
587
601
613
616
619
625
630
668
697
708
717
727
732
749
765
787
809
810
818
819
820
827
835
845
856
872
910
919
9...

result:

ok answer: 200000, maximum: 200000

Test #58:

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

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: 91956kb

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
4
7
8
18
21
22
23
25
29
30
35
37
38
45
47

result:

ok answer: 15, maximum: 15

Test #60:

score: 0
Accepted
time: 1000ms
memory: 208600kb

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: 2259ms
memory: 174512kb

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:

199996
32
44
55
69
77
97
112
114
136
155
156
179
190
209
223
240
242
244
250
256
266
268
273
281
283
287
294
312
315
345
348
351
362
367
389
392
398
401
410
463
467
492
502
523
524
529
531
535
584
591
603
607
626
649
650
657
712
733
747
757
759
764
776
777
784
790
802
808
811
820
827
828
857
861
891...

result:

ok answer: 199996, maximum: 199999

Test #62:

score: 0
Accepted
time: 687ms
memory: 171104kb

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
42
44
48
76
89
93
112
152
153
156
177
199
202
226
232
244
253
265
274
279
286
287
308
310
325
334
335
344
346
352
367
369
370
400
414
421
422
455
457
474
475
491
511
519
535
549
560
610
640
656
664
708
710
728
757
759
776
777
784
798
809
825
831
842
848
856
929
931
933
938
961
989
991
1014
10...

result:

ok answer: 150000, maximum: 150000

Test #63:

score: 0
Accepted
time: 742ms
memory: 168680kb

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
37
48
52
64
73
77
97
117
132
136
141
153
191
199
206
220
240
268
273
279
286
324
350
375
392
403
431
432
455
471
475
506
535
544
556
564
577
588
599
617
627
656
719
728
742
754
776
802
808
809
818
824
931
944
959
971
983
992
1023
1039
1089
1122
1147
1176
1187
1198
1214
1244
1247
1256
1259
126...

result:

ok answer: 100000, maximum: 100000

Test #64:

score: 0
Accepted
time: 932ms
memory: 172016kb

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
18
39
40
44
70
71
77
82
86
114
116
123
153
161
169
176
179
190
193
214
218
220
223
227
231
240
246
250
256
263
268
284
290
308
315
316
330
346
347
367
369
389
454
461
506
524
531
535
557
577
588
595
601
606
626
627
656
657
689
696
728
734
757
759
771
773
780
784
790
809
820
836
840
852
857
87...

result:

ok answer: 170000, maximum: 170000

Test #65:

score: 0
Accepted
time: 2298ms
memory: 180876kb

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:

299727
11
12
14
17
35
38
39
43
69
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
322
331
339
345
348
351
361
364
368
373
375
384
385
392
419
427
430
431
440
441
443
446
459
477
478
489
504
505
508
509
527
533
536
545
550
556
559
566
575
57...

result:

ok answer: 299727, maximum: 300000

Test #66:

score: 0
Accepted
time: 2387ms
memory: 175652kb

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:

249998
10
19
21
27
32
50
52
53
56
73
75
95
100
103
121
137
144
146
149
161
164
172
176
178
201
204
216
218
219
220
223
226
227
248
257
259
265
276
279
299
321
325
332
333
353
354
359
365
367
379
402
405
409
417
451
452
467
481
485
488
490
502
517
528
529
545
549
553
556
560
564
572
573
595
597
599
6...

result:

ok answer: 249998, maximum: 250000

Test #67:

score: 0
Accepted
time: 803ms
memory: 172052kb

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
6
14
21
35
42
44
48
53
103
118
169
178
179
191
206
236
245
254
261
262
263
268
279
283
367
369
401
414
419
422
443
478
482
488
507
511
515
519
520
546
550
568
577
599
605
644
648
662
678
680
694
707
739
764
775
800
810
811
815
820
872
879
924
931
933
935
938
943
946
974
1005
1013
1058
1096
...

result:

ok answer: 150000, maximum: 150000

Test #68:

score: 0
Accepted
time: 2250ms
memory: 180936kb

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:

299626
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
322
331
339
345
348
361
364
368
373
375
384
385
392
419
427
430
431
440
441
443
446
459
477
478
489
504
505
507
508
509
527
533
536
545
550
556
559
566
575
57...

result:

ok answer: 299626, maximum: 300000

Test #69:

score: 0
Accepted
time: 2340ms
memory: 177960kb

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:

249992
17
21
27
32
35
44
52
72
73
95
103
121
132
137
146
149
153
154
172
176
178
200
201
215
216
218
219
220
223
226
248
252
259
265
276
279
299
325
332
333
341
351
353
354
359
365
367
379
402
405
415
418
451
452
467
485
488
490
497
502
517
528
529
545
549
560
564
570
572
573
579
597
599
611
615
617...

result:

ok answer: 249992, maximum: 250000

Test #70:

score: 0
Accepted
time: 975ms
memory: 171740kb

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
6
14
23
34
42
53
102
103
112
117
172
178
196
199
202
206
236
245
254
261
262
273
279
297
310
345
367
369
414
443
482
488
507
511
515
519
520
546
550
568
577
595
605
644
648
662
668
678
680
707
739
757
759
767
788
800
810
811
820
822
855
872
879
924
935
938
943
946
974
982
986
999
1005
1013
...

result:

ok answer: 150000, maximum: 150000

Test #71:

score: 0
Accepted
time: 2355ms
memory: 188640kb

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:

399444
2
6
11
14
18
36
38
40
47
61
62
73
74
77
82
104
122
126
135
138
143
152
157
169
172
176
181
182
183
197
199
204
205
212
219
223
225
232
242
245
250
251
252
259
260
267
269
270
273
280
286
289
299
305
307
322
325
326
334
337
342
343
348
360
362
367
372
375
378
385
389
392
398
400
407
408
410
41...

result:

ok answer: 399444, maximum: 399999

Test #72:

score: 0
Accepted
time: 2255ms
memory: 194028kb

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:

498078
1
2
5
9
11
12
14
16
20
23
25
27
28
29
32
33
34
35
43
48
51
79
86
88
89
91
96
97
112
114
118
120
130
136
139
140
141
148
155
156
158
159
161
162
168
171
173
178
181
182
193
195
201
209
210
211
214
218
219
223
230
231
234
245
249
253
256
260
264
266
269
271
275
277
279
281
282
283
286
290
293
2...

result:

ok answer: 498078, maximum: 499999

Test #73:

score: 0
Accepted
time: 2478ms
memory: 186632kb

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:

399684
2
5
6
13
16
19
24
26
39
44
47
48
71
76
82
85
86
87
98
105
112
121
123
126
136
141
148
150
155
161
162
164
184
190
192
198
199
202
205
211
213
214
217
218
219
227
237
238
239
244
247
250
253
258
261
262
266
274
276
279
291
300
309
310
313
315
324
326
330
338
343
353
367
370
371
378
384
386
394...

result:

ok answer: 399684, maximum: 399999

Test #74:

score: 0
Accepted
time: 2333ms
memory: 197680kb

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:

497506
6
13
14
22
23
29
30
36
39
44
46
53
54
59
61
67
95
97
100
102
108
110
112
121
123
129
132
136
142
149
153
161
166
170
171
204
205
207
213
214
218
229
236
238
244
245
246
247
250
252
254
256
260
268
270
271
273
279
280
284
285
289
294
295
298
303
306
308
324
334
337
354
355
357
363
369
371
372
...

result:

ok answer: 497506, maximum: 499999

Test #75:

score: 0
Accepted
time: 2411ms
memory: 197728kb

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:

499105
2
11
15
17
18
20
23
25
34
37
44
45
46
47
48
49
51
52
55
65
67
68
75
76
77
80
81
82
83
86
90
94
95
97
99
103
107
111
112
114
117
131
133
138
148
152
160
161
167
172
174
177
182
190
191
195
198
199
200
205
210
212
214
221
227
233
239
240
242
244
250
258
260
263
268
271
279
285
286
290
291
292
3...

result:

ok answer: 499105, maximum: 499999

Test #76:

score: 0
Accepted
time: 1469ms
memory: 169616kb

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
29
47
76
98
190
197
199
212
273
279
283
285
390
398
411
414
455
491
506
523
538
548
555
567
601
627
648
780
784
800
818
828
844
913
927
931
940
955
958
991
996
999
1000
1014
1047
1050
1058
1078
1113
1116
1130
1175
1194
1195
1198
1229
1253
1346
1382
1398
1418
1440
1458
1467
1471
1476
1487
1493
...

result:

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

Server Time: 2024-12-01 20:58:37 | OpenSource Project