#Testcases by Samkit Lodha
#Testcases for Minimum transaction

___________________________________________________________________________________________________________________________
// Testcase : 1

//Input :
10 3
1 5
6 10
1 10

// Output :
3
___________________________________________________________________________________________________________________________
// Testcase : 2

//Input :
10 1
2 10

//Output :
-1

___________________________________________________________________________________________________________________________
// Testcase : 3

//Input :
921 57
63 479
309 859
931 997
916 922
86 341
910 952
37 733
321 382
701 942
811 994
683 829
283 870
175 474
211 308
427 463
56 392
302 423
641 656
696 873
477 544
353 885
770 932
1 524
612 690
198 409
887 890
307 310
423 814
958 995
244 780
130 868
281 340
178 899
581 651
952 955
511 732
175 733
686 963
849 994
118 984
591 638
625 649
620 845
531 951
294 898
835 897
455 936
715 877
953 1000
405 814
277 593
282 642
992 998
208 266
610 676
973 997
545 957


// Output :
36

_________________________________________________________________________________________________________________
// Testcase : 4

//Input :
456 70
1 519
33 107
56 168
59 626
66 697
112 651
151 234
177 527
193 296
202 350
226 704
228 493
251 785
260 768
261 904
303 451
309 339
310 353
313 737
315 646
344 619
346 413
382 389
382 692
384 850
387 650
400 992
405 796
424 462
435 445
440 811
444 923
446 787
487 764
507 871
567 699
608 996
612 805
625 643
626 719
626 725
651 772
660 945
679 901
680 993
681 866
691 736
697 746
701 939
712 767
723 801
727 750
736 834
738 912
742 942
753 852
763 848
763 891
786 853
788 841
789 813
800 989
816 867
853 898
856 919
884 997
899 988
900 941
901 913
959 978


// Output :
32
___________________________________________________________________________________________________________________________
// Testcase : 5

//Input :
27 91
1 729
2 112
5 810
17 276
26 64
32 911
37 896
48 432
60 385
66 748
78 166
85 762
99 946
103 591
141 189
146 441
161 308
167 908
186 970
196 685
197 974
207 246
209 711
219 943
228 323
229 557
244 766
248 302
252 631
258 820
259 282
264 439
305 771
315 664
320 496
339 528
345 394
348 845
382 640
392 591
427 792
435 928
457 935
473 941
494 586
499 844
500 958
501 673
514 677
572 598
584 704
584 747
587 945
602 940
608 982
609 851
611 793
617 705
624 922
631 981
640 807
648 867
655 963
689 794
706 811
707 711
716 887
716 937
719 886
733 978
740 761
742 866
765 775
765 859
765 862
783 861
784 787
794 945
810 868
823 907
833 920
835 868
869 919
869 930
887 900
892 931
921 964
949 987
964 966
964 971
968 970


// Output :
7
__________________________________________________________________________________________________________________________
// Testcase : 6

//Input :
530 96
1 801
13 187
17 18
24 202
99 749
116 609
117 720
119 583
133 812
143 660
148 314
149 171
159 746
164 534
175 886
178 346
183 852
189 663
196 327
205 465
215 660
218 798
249 444
250 775
251 561
262 318
280 557
282 667
288 317
288 579
296 430
310 483
323 489
336 605
341 623
368 962
369 981
370 661
376 747
408 457
444 705
445 942
452 711
462 841
473 630
475 776
476 602
485 694
493 770
499 566
500 944
520 897
531 988
561 680
621 696
625 835
640 918
658 907
672 693
679 982
684 940
688 712
703 791
703 856
722 832
730 810
732 807
733 766
733 921
736 988
739 871
756 981
758 794
758 842
771 861
779 831
812 910
819 965
826 997
839 901
842 928
844 891
848 861
848 925
858 882
869 921
887 959
896 989
904 916
908 921
936 985
947 969
970 994
977 998
990 994
996 1000


// Output :
33
___________________________________________________________________________________________________________________________
// Testcase : 7

//Input :
672 90
847 977
391 979
889 951
488 691
832 918
838 911
410 746
92 963
772 847
945 999
645 696
663 962
745 958
841 875
520 965
914 918
18 465
739 758
304 514
351 551
398 501
615 682
471 693
535 835
612 613
229 958
419 701
379 614
529 712
663 806
538 676
774 945
907 938
68 636
971 977
261 632
500 564
235 566
727 739
859 938
508 754
544 750
477 699
955 975
893 911
429 844
711 878
680 874
211 397
18 706
582 845
317 367
789 815
140 253
100 213
571 881
278 938
518 985
178 345
186 865
700 994
481 873
876 988
578 678
206 906
359 689
660 728
169 596
839 918
405 842
9 983
227 281
164 776
69 660
381 845
72 458
400 838
293 530
43 694
297 309
263 906
162 549
736 920
341 682
147 700
735 1000
549 704
425 916
828 871
246 360


// Output :
-1
___________________________________________________________________________________________________________________________
// Testcase : 8

//Input :
630 33
983 993
368 748
181 910
243 854
758 913
958 969
836 965
928 975
759 890
416 657
64 933
447 904
848 878
8 589
263 350
451 882
899 924
960 997
325 902
320 737
852 983
817 973
145 208
732 954
45 65
384 424
428 667
508 664
637 799
969 983
589 860
394 977
163 671


// Output :
-1
___________________________________________________________________________________________________________________________
// Testcase : 9

//Input :
370 90
1 259
7 437
18 736
20 452
83 787
112 210
135 863
142 525
149 882
152 554
158 889
160 789
164 871
193 934
216 800
227 656
230 463
230 843
235 420
246 957
253 298
259 787
267 357
290 429
292 587
297 885
301 327
302 687
321 412
329 332
329 453
335 931
336 787
338 881
372 635
393 473
411 992
424 463
447 505
448 728
450 647
452 803
465 659
483 722
496 838
503 751
504 845
512 813
518 864
520 567
520 846
526 987
535 601
536 596
552 741
573 813
579 859
579 973
595 795
618 926
625 989
631 671
632 727
634 874
651 683
665 823
666 892
687 957
698 858
705 713
712 958
727 874
752 782
758 788
760 896
770 990
797 990
801 806
807 928
834 912
857 895
862 901
872 878
877 878
877 995
892 903
906 971
915 976
963 1000
971 993


// Output :
23
___________________________________________________________________________________________________________________________
// Testcase : 10

//Input :
274 86
1 149
49 676
58 395
122 328
125 173
129 608
131 612
137 644
139 445
161 276
169 871
214 225
214 379
232 709
238 531
249 274
268 786
271 380
273 881
274 905
278 895
292 423
300 351
329 657
337 445
342 779
360 562
371 908
372 937
381 823
382 759
384 669
408 560
409 462
440 930
442 792
448 723
469 670
475 892
490 677
490 718
496 928
509 626
533 818
537 754
538 544
542 841
544 814
553 908
557 752
572 761
594 817
610 899
635 716
635 771
642 906
649 676
653 732
656 780
657 826
676 702
678 734
691 849
694 697
699 960
704 718
706 814
720 776
721 756
731 814
731 917
738 907
758 932
778 940
788 858
811 965
814 873
823 939
839 849
841 868
858 928
873 890
896 944
901 962
939 959
997 1000


// Output :
48

___________________________________________________________________________________________________________________________
// Testcase : 11

//Input :
320 71
1 972
10 606
17 891
29 293
68 381
76 449
98 430
106 301
109 757
163 763
175 314
201 998
202 797
230 612
253 865
257 555
297 483
318 582
319 638
331 861
351 873
354 823
384 576
396 405
399 506
407 986
435 451
451 525
454 598
454 851
464 956
469 817
509 890
516 698
526 979
531 573
536 701
565 823
580 749
583 954
597 907
624 654
645 762
674 978
690 891
696 811
703 712
709 959
715 995
739 949
742 933
744 833
776 877
779 785
782 912
783 881
791 802
797 818
808 935
813 925
819 984
873 932
876 967
890 919
892 927
905 963
934 985
975 992
992 1000
994 996
996 999


// Output :
19

__________________________________________________________________________________________________________________________
// Testcase : 12

//Input :
1000 60
1 661
3 131
5 155
29 834
31 667
42 506
77 948
83 914
111 351
112 699
112 760
116 910
132 413
147 476
162 909
164 590
208 447
225 956
231 818
287 480
298 851
310 516
324 783
326 823
347 863
377 449
384 568
396 735
431 520
439 619
460 468
486 508
516 697
560 566
578 999
587 713
600 623
621 870
623 767
628 691
637 855
650 796
689 875
721 842
746 931
756 887
774 945
785 827
789 839
795 991
848 899
859 981
868 957
872 964
886 976
915 994
941 990
951 1000
984 986
985 995


// Output :
19
___________________________________________________________________________________________________________________________