uva11678測資A

Input:
1 1
1000
1000
3 4
1 3 5
2 4 6 8
10 9
1 1 2 3 5 7 8 8 9 15
2 2 2 3 4 6 10 11 11
2 2
1 3
2 3
3 2
1 1 3
2 2
2 2
1 100000
1 100000
3 5
26 30 31
26 27 28 29 30
4 3
11 31 31 40
12 32 40
8 8
1 1 2 3 7 7 8 10
2 2 2 4 5 6 9 9
7 5
9000 90000 99000 99900 99990 99998 99999
9 99 999 99999 99999
6 8
100 200 300 400 400 500
123 300 345 400 567 700 890 1000
5 10
99 101 103 105 109
101 101 101 101 101 101 101 101 101 101
6 11
1588 5674 15934 54882 64715 84561
154 256 849 852 904 1588 5674 15934 54882 64715 84561
23 29
4 85 629 663 668 723 800 883 921 1112 1197 1204 1287 1368 1538 1601 1646 1701 1754 2181 2181 2829 3016
16 20 85 322 1632 1873 1927 1979 2008 2039 2181 2243 2269 2309 2360 2401 2408 2584 2594 2614 2640 2696 2811 2829 2895 3016 3052 3080 3101
8 9
66 300 555 555 954 1205 1205 46872
954 1002 1205 2015 2015 2019 6548 12546 90002
7 10
13 50 80 141 180 318 319
21 59 59 141 242 278 282 319 354 453
14 14
9988 10116 12428 12428 23513 34601 55635 71140 80714 84826 95941 96119 97103 98113
34601 40271 53106 53177 54256 55635 60718 61796 71140 71140 71274 75951 84379 95941
16 38
39 65 135 163 207 599 699 849 875 1054 1156 1218 1453 1481 1539 1548
89 217 278 288 453 533 598 641 660 671 722 805 949 1013 1112 1197 1202 1308 1583 1600 1631 1674 1697 1754 1754 1756 1867 1970 2037 2129 2234 2250 2292 2406 2412 2457 2559 2593
50 55
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
18 20 22 24 26 99901 99902 99903 99904 99905 99906 99907 99908 99909 99910 99911 99912 99913 99914 99915 99916 99917 99918 99919 99920 99921 99922 99923 99924 99925 99926 99927 99928 99929 99930 99931 99932 99933 99934 99935 99936 99937 99938 99939 99940 99941 99942 99943 99944 99945 99946 99947 99948 99949 99950
25 62
22 53 91 143 232 325 407 733 810 918 1074 1149 1161 1197 1288 1456 1488 1541 1740 1740 1821 1883 1969 1969 2117
57 69 123 242 278 326 345 407 479 516 594 629 663 668 723 800 883 921 1017 1112 1197 1204 1288 1368 1541 1601 1632 1646 1740 1754 1754 1758 1785 1883 1927 1979 2008 2039 2181 2243 2269 2309 2360 2401 2408 2446 2584 2594 2614 2640 2696 2811 2829 2895 3016 3052 3080 3101 3127 3139 3225 3238
69 61
281 370 836 871 1169 1287 1396 1493 1714 1836 1920 2035 2427 2527 2777 2819 2905 3012 3143 3205 3457 3558 3710 3904 3975 3994 4027 4527 4575 4887 5003 5044 5078 5141 5152 5449 5473 5522 5536 5558 5719 5768 5838 5865 5948 5955 6013 6027 6037 6053 6344 6371 6402 6504 6621 6715 6731 6947 7053 7432 7502 7533 7651 8016 8114 8120 8273 8333 8389
68 267 321 450 518 567 669 919 1021 1042 1193 1263 1533 1601 1637 1751 1751 1819 1840 1979 2030 2130 2230 2300 2464 2572 2593 2637 2685 2847 3097 3245 3330 3334 3406 3571 3694 3748 3762 3772 3823 3957 4039 4161 4291 4386 4411 4429 4504 4526 4651 4807 4838 4861 4880 5012 5214 5327 5526 5772 5776
90 83
16 76 80 153 301 558 666 794 993 1079 1170 1209 1437 1524 1587 1810 1866 2056 2125 2219 2265 2499 2535 2790 2889 2965 3011 3138 3181 3442 3551 3829 3958 3973 3990 4052 4095 4245 4492 4556 4745 4903 4944 4971 5041 5085 5130 5155 5290 5473 5503 5545 5598 5741 5777 5824 5849 5879 5948 5990 6014 6017 6038 6143 6195 6382 6481 6497 6620 6718 6754 6817 6993 7396 7462 7531 7644 7989 8109 8122 8254 8361 8456 8511 8521 8534 8556 8646 8973 9057
100 280 333 378 539 579 663 676 683 795 833 1018 1083 1194 1213 1418 1518 1600 1627 1650 1754 1754 1813 1888 2010 2022 2132 2246 2273 2353 2547 2565 2593 2637 2708 2719 2884 3076 3175 3247 3328 3334 3426 3534 3573 3682 3731 3761 3763 3911 3979 4062 4195 4298 4344 4401 4487 4496 4540 4566 4656 4809 4854 4859 4912 5019 5188 5332 5386 5689 5773 5800 5868 5868 5885 5887 6024 6096 6147 6155 6292 6365 6382
0 0
Output:
0
3
4
1
1
0
1
2
4
3
3
0
0
18
4
5
9
16
45
17
60
80