#Testcases by Samkit Lodha
#Testcases for Minimum time for construction

___________________________________________________________________________________________________________________________
// 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 :
164 85
52 71
133 148
95 103
57 128
150 162
17 153
149 163
59 124
104 124
130 137
135 138
29 58
27 106
113 128
2 86
122 132
58 157
106 136
84 99
140 159
12 152
123 140
95 115
17 154
65 95
48 91
51 152
159 161
112 118
89 131
73 100
16 159
159 161
159 162
70 137
61 90
132 158
7 95
116 134
26 53
152 154
93 115
17 66
132 137
154 159
105 145
121 134
70 163
125 162
95 124
65 158
70 86
153 160
66 102
129 133
60 112
91 135
157 159
82 151
138 164
87 143
62 98
78 153
88 103
26 85
97 149
107 128
135 141
79 145
2 42
7 57
94 162
135 149
64 125
27 46
162 163
44 95
94 99
108 159
129 136
101 156
77 112
104 162
23 146
22 69


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

//Input :
658 73
253 285
196 236
179 243
71 657
644 650
204 285
252 414
389 436
27 126
305 375
345 462
241 339
248 341
298 331
153 422
314 607
65 654
542 624
381 595
643 657
435 542
284 443
443 554
548 624
319 354
52 127
159 530
151 361
439 535
139 656
453 529
571 649
5 231
43 296
592 622
452 498
165 500
17 466
646 653
601 605
390 489
45 135
353 446
116 312
349 479
374 580
656 657
566 641
418 543
435 497
100 658
32 435
65 569
99 491
164 376
171 441
58 606
262 350
633 650
449 483
290 321
17 528
467 543
466 584
527 535
590 646
338 595
320 431
592 593
394 589
509 632
35 100
578 625


// 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
___________________________________________________________________________________________________________________________