#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 :
367 48
51 198
100 247
41 280
104 132
333 340
359 360
60 174
249 336
177 338
307 355
258 286
81 162
265 276
299 304
26 53
221 242
62 174
118 192
213 284
227 299
169 367
353 355
339 350
168 198
255 323
354 362
50 114
125 252
154 280
263 323
344 364
305 309
152 269
100 167
111 281
183 344
211 343
292 333
210 290
357 367
225 325
112 127
1 223
265 277
294 323
239 352
325 360
7 31


// Output :
14

_________________________________________________________________________________________________________________
// Testcase : 4

//Input :
451 89
233 305
363 444
426 435
388 401
98 410
222 378
320 330
402 425
235 322
59 122
191 278
168 205
299 383
230 428
315 381
385 438
32 62
359 413
292 415
228 437
100 174
179 364
390 447
194 330
387 445
446 451
317 322
160 325
69 409
311 356
218 339
118 280
67 105
113 124
443 449
124 313
67 202
249 372
412 427
262 450
196 273
33 202
325 430
227 353
418 433
240 296
89 123
353 377
34 317
278 279
288 386
364 416
376 391
3 39
312 411
67 95
382 419
106 402
290 360
28 34
256 366
431 443
300 323
149 381
305 436
77 113
146 188
431 443
296 337
249 412
1 157
81 286
97 381
50 411
312 347
240 286
94 151
316 410
332 351
58 206
186 438
406 447
347 432
396 405
218 270
362 382
335 445
11 252
94 178


// Output :
9
___________________________________________________________________________________________________________________________
// Testcase : 5

//Input :
69 88
61 62
41 57
41 66
21 33
44 65
32 58
63 67
61 62
30 43
41 56
49 67
44 54
60 64
46 50
19 33
43 63
63 65
21 37
21 39
2 23
41 66
24 44
49 50
24 50
47 54
34 61
34 40
65 68
51 57
57 66
39 42
1 54
27 62
46 47
17 31
67 68
13 51
9 55
3 69
52 69
1 11
28 54
49 51
42 64
53 64
55 65
8 15
24 28
54 62
65 69
25 64
44 52
37 41
22 45
12 50
41 52
33 54
19 51
12 68
10 21
67 69
20 43
43 65
34 59
45 64
6 64
40 47
41 55
1 60
6 43
29 40
26 55
29 68
59 68
57 63
5 13
10 19
43 60
50 58
36 67
5 32
21 61
52 53
27 64
30 61
61 62
50 52
24 28


// Output :
2
__________________________________________________________________________________________________________________________
// Testcase : 6

//Input :
439 78
290 369
204 232
68 167
123 226
130 308
348 376
40 65
297 404
399 421
235 269
174 217
177 348
82 222
30 327
310 319
114 224
367 438
382 390
233 288
235 401
58 297
328 429
376 439
333 334
282 310
159 171
103 375
433 434
230 253
71 211
49 271
217 315
30 130
316 431
301 351
275 368
297 438
170 403
1 86
135 346
96 192
162 321
207 314
305 400
328 336
74 179
364 380
167 428
235 372
152 391
172 434
349 433
279 333
337 394
289 399
77 427
273 384
48 427
180 366
298 330
371 438
366 384
30 125
90 325
31 401
206 416
215 298
74 362
158 211
133 238
46 159
11 46
195 429
196 310
199 290
417 421
209 400
107 414


// Output :
15
___________________________________________________________________________________________________________________________
// 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
___________________________________________________________________________________________________________________________