TEST DATA FOR `ontherun'

Input for test 1

4 10
1
9
11
19

Output for test 1

44

Input for test 2

2 5
3
7

Output for test 2

8

Input for test 3

2 5
2
7

Output for test 3

9

Input for test 4

3 5
8
9
4

Output for test 4

12

Input for test 5

3 5
8
10
12

Output for test 5

15

Input for test 6

5 21
4
19
22
28
48

Output for test 6

124

Input for test 7

50 6579
536155
719633
538331
973909
338759
205140
302715
428145
588278
643335
598898
584886
561878
57081
595449
150324
154838
750653
773107
285619
892356
97245
525577
593276
779192
907846
178222
136019
214298
882264
300293
631312
998080
151290
465204
230474
738981
185736
299083
241921
365312
808039
618500
923513
624910
832959
202683
7141
332074
76383

Output for test 7

23698366

Input for test 8

100 411428
430857
54435
624526
287705
286213
442598
286094
385034
343233
286668
885069
258760
71397
28779
107225
978623
715403
829369
633978
380246
601893
501170
709975
432367
502770
868316
97342
230323
782252
551354
792200
258939
855298
687139
157995
833739
764121
359360
815841
580057
78686
975379
592803
574990
503794
615906
573394
315344
452185
596548
227227
21751
858785
408388
236478
309377
869621
595649
951528
891403
960018
432234
932946
503257
5564
878913
254890
492082
847216
845612
751466
683824
725185
308098
176920
974612
387304
98234
956337
176633
754183
917517
350362
642775
309086
233909
110317
88065
204274
584018
114567
386763
782232
491705
749542
347470
410076
758469
516146
28312

Output for test 8

70971938

Input for test 9

500 922743
515993
625382
572481
250226
738570
166303
814317
632986
646822
373228
883337
705296
481141
26315
946248
361058
175716
686641
178707
147880
206277
600908
139547
558127
650672
62495
937916
227489
689440
729675
68937
184194
574006
909967
72423
557800
369202
86360
854869
107131
176040
421103
475612
692313
717301
763594
942485
354044
45414
901370
489849
10291
147708
721396
462697
300822
582604
339680
235191
745774
201319
561016
121786
906204
978600
650625
456014
491140
993847
942147
518492
523498
437258
331278
785000
511534
946720
974230
671323
656053
657725
240721
98364
117631
634263
81507
453893
261876
172433
832522
941815
161601
175182
166681
582327
858266
996481
448724
843716
444733
972328
379505
776383
729118
185881
218452
700017
455101
761958
434273
724667
995541
324923
695096
314995
389768
872178
214186
524385
174701
667089
613070
612478
858402
309985
350715
337378
122310
639244
48486
994131
13825
797303
572551
106688
930922
685461
827641
814582
109890
158621
881435
311725
439234
974669
243042
967545
648209
526345
31074
905130
496820
325449
8766
132777
342660
674666
360589
770718
24249
811601
915261
320625
104197
418760
765338
269426
210294
903768
828273
969066
128413
423332
475698
698982
895944
675196
517416
997583
954395
953009
358307
783049
309191
553862
296936
902845
55837
66813
654452
626883
835065
338511
614588
193123
123965
509916
426788
929085
432163
712775
534075
201493
706755
88106
498195
622826
639911
289386
522337
592311
280014
623872
335588
534946
860057
295584
75056
681124
143320
687749
156647
97623
741416
371214
492036
25052
757415
174521
518916
624866
48623
592546
548724
608897
269540
451130
788370
174836
353684
757761
900915
351591
9353
241600
178554
559079
253334
174121
806804
588307
680409
634014
501523
631015
585779
672178
153822
645438
820868
595573
378328
588582
297080
339026
837294
618841
861932
163958
419431
659717
190526
510383
253762
990120
773680
46739
804413
204394
781528
890472
43894
771430
855324
705259
765512
963232
876126
278944
248216
456169
700578
125436
711001
910219
292935
275745
723481
171084
748660
385100
112070
925903
356356
507648
8291
74764
117653
816037
820866
297409
403177
374287
823689
228122
609258
28542
187508
872968
565131
46881
47725
874404
872658
317360
200350
551149
516799
469427
312600
309411
720083
26
886476
668806
711221
410002
338781
297054
497770
52171
378313
766755
864838
188926
742593
291007
233446
999034
377504
158518
98899
570851
332057
560143
5043
398421
228568
704999
196236
449495
840376
683615
605279
407573
452621
206727
890295
376552
637243
780832
112835
864884
385335
865374
967590
690424
205232
272269
423278
37129
513530
337519
235244
985773
71867
928956
141476
683849
211251
6180
82040
931500
447511
461639
492172
372758
838832
229422
444414
992586
35047
925051
66473
43519
587458
490377
478078
440361
349406
768370
289435
661960
26862
569338
131480
146098
413287
449861
467531
432777
45308
86068
119040
44438
880028
151869
154682
446000
758644
19322
500141
826000
475350
281742
361660
820972
9207
100554
184086
372647
146831
124923
826062
381325
275514
300127
201754
684191
463233
228365
158668
645389
170146
976843
511437
561987
615402
835589
186913
448743
215930
645414
439362
112636
836286
969125
227297
829042
259428
731538
594642
214199
179658
561724
335965
898011
706009
130530
243910
447615
375492
374659
810314
301474
742142
862987
682678
637643
914472
309590
344371
525492
848317
629774
98414
70514
604954
119884
276807

Output for test 9

281705993

Input for test 10

1000 715760
133997
679189
722484
166448
338576
655718
218334
287126
162491
5730
249796
30794
374750
923236
740006
208780
789534
902271
47135
698283
282890
556636
577873
312536
475382
286616
771955
594092
557850
543488
583324
924393
537934
950785
862481
608538
464038
808057
730233
544820
582667
962830
993741
853990
561722
827281
400176
381377
789191
528641
450883
332057
772351
110525
149753
819501
21027
93213
364127
743851
719493
4676
6443
937837
460528
114138
461641
774797
332978
142602
191940
601197
487482
249653
239788
190314
736048
865708
55718
497288
817793
669417
224592
989829
248784
120239
916609
722574
497716
818240
303957
683991
935847
652191
456469
168165
209496
241320
947070
483540
502486
807146
287543
8366
485858
14101
495592
818235
500053
879021
323928
52549
853628
910707
610643
140293
740692
745676
627585
585247
630896
691951
390274
409269
540635
479529
470614
589884
87451
797255
634008
3844
912486
727760
458076
928335
944861
284392
224215
60957
109110
919386
689405
131466
740375
76760
618480
403787
985231
775430
101527
945119
407958
449990
2818
287498
487559
173617
333047
671487
540120
217996
742463
165315
210231
150449
676451
647568
185779
263159
385166
557322
359606
711238
944025
910425
712280
896136
621313
890576
660914
162589
363246
213227
213768
27886
285861
871469
708975
882055
938692
76533
183477
289787
699001
549899
16202
796089
70046
486071
684099
47330
385611
739741
543322
350161
599566
181247
48241
718658
487985
871180
811706
423812
877437
217893
220098
931319
991986
667896
790969
468642
879692
634258
209781
828898
223688
265709
631417
128648
890952
601016
773400
273786
941726
519168
968212
740054
772997
394057
354798
783137
749998
278712
962541
401687
380249
893110
528967
782169
486028
363406
464848
757176
254515
79717
672511
162250
702192
802895
686139
236685
333874
184886
353143
190805
350211
677094
545594
268578
44415
719698
978026
535891
303689
543269
426228
890375
808520
611461
569892
540355
409162
7549
415029
263546
699723
63462
150226
908816
343041
471539
229996
828131
701688
558162
100376
655285
669969
464576
943744
220878
787644
631668
44338
500034
147566
258337
301784
624532
826656
661565
251039
901441
503158
652845
903334
916096
144401
930741
289311
561807
620034
921582
763506
838352
418656
656534
685335
555744
313924
908301
807898
431596
473486
507589
630195
195549
654801
179242
664149
131509
451179
370055
364281
370036
94780
951858
709701
264274
787236
770242
725643
371632
499813
244787
711009
151495
391296
412642
490962
161111
551011
323677
546658
675157
445634
750215
560719
610149
880874
53616
445332
946839
272923
368089
744171
508967
740355
211305
889289
675564
796253
232353
885156
29652
954588
158725
835002
935110
216910
532359
336321
895291
418311
534953
184808
294341
669233
927959
337215
720909
406382
783912
506942
693006
776889
502389
680804
864239
530483
403197
845998
20693
231212
616968
163318
652700
260018
772798
91882
88059
739764
165590
703925
37509
543354
302380
782531
567136
952106
434964
693595
566687
214994
421935
404142
521484
259758
890820
86604
65770
554918
633005
222389
347128
688655
730813
983508
568394
578250
436294
429099
301702
454929
971618
970967
848445
376562
456389
921038
311869
138630
170694
281714
371322
106572
495413
340993
418073
845053
622484
917008
603915
27597
564864
106018
40847
169616
14309
234306
401229
326115
168471
23710
234367
259778
78966
144459
622141
333868
238814
754599
230620
776272
739061
985610
217616
145440
166597
817224
871506
95968
602363
345050
781763
571824
303808
52167
976395
669979
437965
585680
959441
828476
170668
462338
299102
53133
439802
600275
163691
349472
351139
128982
490920
754777
667089
364647
772094
643815
722892
466386
405338
725847
40483
189867
343222
165614
235026
422987
155220
993500
668301
184090
422667
756739
920457
362547
564701
682078
78870
326101
192719
338768
209775
266298
45725
418017
143097
725570
560550
180394
899519
585434
473121
906315
85609
99099
276881
247194
320168
543050
332290
287481
3305
226493
330377
852512
347819
935611
270024
736418
736952
168293
172629
71418
908375
516252
191676
648495
774426
323459
294369
154090
534208
855696
216855
673077
103476
985196
295655
480659
350661
171298
130991
801102
577418
913249
871086
436428
593354
990699
451584
690806
408865
582640
65643
954587
387171
673802
865639
424503
864684
191601
747634
372935
53925
755262
588727
929362
99551
215639
492214
681781
658075
789405
146309
366408
336053
279947
972352
202117
848519
880456
184428
894511
275984
389032
513615
226334
309353
363218
179523
349936
710538
100252
685012
178132
293626
162775
336118
547029
786320
57060
670185
403977
781506
206547
536290
101951
279644
408120
691557
795343
777903
888006
936289
908860
533300
30037
944630
59155
144468
988561
693383
656767
418021
144319
340424
603263
147044
652621
349911
65328
795112
873269
851143
684437
592000
980570
601781
839095
477225
514881
407461
678290
23527
555342
535029
692319
611007
833380
105386
73690
958859
750548
926803
180175
738384
459942
946492
68660
549511
981542
876062
487319
532456
577194
457383
450402
374002
155574
854458
770966
349542
421460
312544
779004
291180
453138
249350
133244
290624
778336
519347
762576
413132
229843
608562
806327
423468
569987
814772
110925
292803
266635
90461
673941
180959
836713
670467
85598
363840
815897
73126
824070
721698
900641
706126
425999
518787
891960
482804
430280
215644
266016
370695
324468
466653
36743
164576
892820
600616
858434
466765
647608
172025
354773
537075
835746
344731
534412
465561
656834
245239
956505
848307
252559
145324
403115
588275
68009
626797
74881
581066
820421
296713
393577
314044
408204
289078
27272
944129
161780
667113
673685
315709
277044
964522
883428
929368
622284
839325
981231
821542
300751
101864
169793
115110
955154
990287
662736
54482
278905
350624
191512
252502
154719
511350
232322
709949
267136
878916
585682
684376
565609
204152
560774
399155
113345
740821
532891
815005
309144
126220
384027
606899
270723
326900
648786
174373
14733
805923
680680
991135
547763
655092
953425
102010
821662
598184
609715
786188
823616
889116
473364
713138
625404
410344
122473
662324
656545
7611
969915
603837
582653
891830
67038
641408
143921
989657
6753
702103
960561
451809
588513
571757
354090
230939
70998
778147
518194
145736
895299
224833
143629
159696
744157
389969
742012
554744
9322
292240
197907
182742
982750
459167
422232
271045
947258
433583
688534
159209
413223
247177
253190
498059
890165
54041
28206
573327
171654
233537
368401
575721
290526
675094
821595
457392
226070
285508
979762
949421
538551
602652
260380
902266
307592
552296
580405
215302
763714
93925
891139
685067
546406
717341
492004
395157
582812
377656
896783
142403
659511
598553
889851
520889
122481
691949
775320
922350
69411
599112
822834
941550
441914
969732
574219
659509
646431
180353
160467
505193
560650
923933
644235
934875
862025
353481
845428
913316
656659
62833
213538
105881
16437
168292
307585
97393

Output for test 10

671598965