P20519 [HackerEarth] Chandler is participating in a race competition involving N track races. He wants to run his old car on these tracks having F amount of initial fuel. At the end of each race, Chandler sp
普及
题目描述

Chandler is participating in a race competition involving N track races. He wants to run his old car on these tracks having F amount of initial fuel. At the end of each race, Chandler spends si fuel and gains some money using which he adds ei amount of fuel to his car.
Also for participating in race i at any stage, Chandler should have more than si amount of fuel. Also he can participate in race i once. Help Chandler in maximizing the number of races he can take part in if he has a choice to participate in the given races in any order.
Input
First line will contain T denoting number of test cases.
Now in each test case first line will contain 2 integers F and N denoting initial amount of fuel and number of tasks respectively.
Next N lines will contain 2 integers si and ei denoting fuel spent and amount of fuel he adds after participating in race i.

Output
For each test case output maximum number of races in which Chandler can take part.

Input Constraints
1 ≤ T ≤ 10
1 ≤ F ≤ 1000
1 ≤ N ≤ 100
0 ≤ ei < si ≤ 1000

SAMPLE INPUT
2
10 2
8 0
4 2
5 1
10 0

SAMPLE OUTPUT
2
0

输入格式

见题面

输出格式

见题面

样例输入
10 669 43 35 13 679 335 947 30 938 524 236 84 68 46 790 231 29 18 828 761 346 132 679 589 979 379 23 0 380 356 921 843 431 149 219 194 342 92 204 134 405 34 987 394 246 58 946 689 909 525 515 36 791 241 708 521 421 124 950 149 18 16 552 463 530 389 261 147 934 721 854 681 255 59 513 255 968 249 126 56 935 775 187 132 185 155 846 9 976 48 757 66 370 137 145 3 77 46 121 117 868 81 403 70 518 429 975 911 77 43 417 37 92 62 440 36 849 234 234 65 784 757 520 304 298 117 403 317 420 175 88 47 201 109 114 59 109 41 907 204 891 653 900 334 926 310 611 501 976 483 301 62 185 161 616 425 188 169 208 86 245 156 950 545 488 454 515 98 854 234 486 296 744 304 431 416 724 384 146 140 236 129 809 139 321 252 254 60 794 378 171 31 459 277 835 107 887 785 598 353 122 114 188 56 468 213 589 280 10 3 593 83 883 279 17 8 529 263 415 408 82 12 711 256 705 642 541 326 599 320 682 335 221 109 641 18 839 662 582 44 315 105 445 148 279 170 752 46 82 80 480 194 103 53 758 54 791 149 101 34 789 85 165 80 356 124 401 354 385 253 42 38 860 206 248 209 299 133 296 284 221 35 247 55 20 4 482 98 655 29 551 463 69 58 803 325 871 31 617 410 241 69 306 195 497 314 941 601 608 88 175 27 714 359 151 82 778 170 895 241 919 583 226 212 512 363 762 222 935 212 990 424 388 70 978 161 552 157 31 3 857 87 338 147 330 120 6 4 825 725 890 704 698 478 433 86 495 343 943 64 923 99 955 882 579 204 546 431 201 68 640 496 485 301 978 177 817 596 273 116 235 16 87 56 629 468 493 64 416 178 903 508 367 96 1 0 140 117 426 137 826 744 748 585 745 181 475 263 411 393 906 885 613 56 929 85 215 150 715 430 208 128 321 121 825 297 222 205 570 148 7 0 415 83 408 126 182 58 424 279 333 42 589 269 26 11 537 479 290 252 574 10 571 117 774 210 566 402 62 27 345 174 586 84 525 143 622 549 580 304 298 169 726 409 209 176 403 61 695 399 700 667 893 841 514 264 369 31 13 2 918 889 202 11 820 445 849 102 432 51 190 168 691 412 966 294 370 10 348 347 765 458 683 50 20 15 27 6 627 440 522 463 101 51 751 280 800 798 65 5 26 21 311 218 872 588 319 270 997 369 656 584 416 346 121 84 238 185 527 327 539 100 112 78 474 45 262 211 813 61 504 13 283 163 906 868 443 412 747 451 594 200 903 38 445 229 149 89 874 534 250 161 779 630 402 215 926 585 525 37 693 438 928 551 547 544 130 50 761 316 131 89 982 432 68 33 759 57 812 528 946 510 396 335 125 24 328 257 165 103 140 56 584 226 832 129 603 307 822 3 541 355 422 217 688 32 300 298 56 30 783 178 523 269 429 289 679 305 48 18 959 558 52 34 253 27 728 599 900 549 571 366 205 131 313 49 832 819 43 38 74 64 591 344 354 58 594 452 126 53 579 281 828 333 331 244 569 532 640 227 959 635 259 224 905 675 408 71 887 451 326 75 978 411 908 14 287 24 67 41 494 399 848 313 627 451 106 72 236 32 14 7 10 1 709 374 195 82 353 23 269 57 392 61 593 414 281 126 152 18 643 143 344 65 670 452 20 6 869 406 575 207 152 84 506 500 849 678 680 320 484 248 878 861 898 338 878 103 53 10 877 432 378 9 889 282 542 371 526 168 514 243 645 579 684 237 877 564 554 506 85 66 209 190 264 81 488 437 636 336 874 9 939 411 83 0 650 224 86 54 35 30 626 228 968 940 180 175 545 334 456 268 122 65 294 176 122 31 230 98 26 3 972 135 706 147 495 419 30 21 881 756 883 324 446 375 167 71 397 147 62 42 691 199 868 296 624 596 118 108 801 263 308 207 810 713 178 69 720 406 236 80 623 331 107 96 671 653 45 13 336 130 623 578 993 774 714 333 183 9 821 105 677 257 107 53 845 210 142 28 843 615 517 261 198 166 884 111 599 97 639 189 739 683 312 98 455 14 51 46 208 94 325 84 702 10 722 668 419 97 111 94 592 322 77 71 601 7 9 1 944 166 485 378 612 163 117 98 524 478 407 311 741 463 967 399 866 735 340 43 903 828 896 726 428 63 284 23 635 168 931 520 643 561 612 593 914 491 23 7 598 407 520 337 864 77 780 20 877 138 364 251 921 455 274 13 582 502 432 8 552 41 147 117 480 117 151 121 838 665 533 341 307 2 125 21 241 162 603 470 726 361 249 11 577 497 698 407 782 244 726 640 842 465 879 721 982 746 417 102 554 66 957 130 353 339 86 8 688 631 62 45 357 202 411 211 535 292 443 42 588 207 353 314 744 342 453 433 611 54 247 64 818 588 80 1 988 396 466 350 204 83 88 32 541 226 845 702 958 824 95 52 807 99 30 21 381 80 978 953 703 359 860 191 130 78 393 337 456 362 144 26 738 350 571 44 81 53 57 26 54 23 640 339 302 242 113 53 503 495 26 5 665 489 77 54 175 21 263 0 32 21 289 72 637 233 750 568 626 290 459 76 662 93 891 330 119 42 997 625 445 213 826 365 610 144 904 728 428 1 414 208 572 477 579 289 265 152 980 141 486 176 273 192 240 203 814 363 519 481 979 214 536 99 72 0 762 532 929 885 493 254 351 311 748 232 327 214 609 490 606 39 448 101 945 92 393 374 45 5 919 139 226 199 883 250 303 256 976 678 537 13 277 199 235 86 168 152 740 427 570 446 925 717 927 169 705 678 978 822 582 174 828 574 406 347 455 112 57 44 291 219 601 188 184 2 295 47 99 46 182 142 83 78 38 24 327 31 328 31 194 80 904 348 419 340 434 42 369 256 655 280 787 55 930 59 442 355 672 419 610 132 912 364 959 578 53 32 42 31 292 67 992 43 960 369 209 46 635 303 884 792 940 229 895 510 992 479 444 134 580 525 868 846 450 27 440 261 814 644 234 188 68 20 4 3 339 184 773 114 845 130 613 387 677 185 356 51 195 135 35 18 908 157 264 92 431 379 859 505 536 427 52 30 372 307 334 153 323 101 682 34 113 94 654 5 801 76 161 146 512 162 120 58 448 326 128 13 438 79 825 499 781 618
样例输出
0 24 4 2 22 18 0 25 6 11