TEST DATA FOR `corral'

Input for test 1

3 4
1 2
2 1
4 1
5 2

Output for test 1

4

Input for test 2

100 100
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1

Output for test 2

1

Input for test 3

9 9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
1000 1000

Output for test 3

1000

Input for test 4

2 2
1 10000
10000 1

Output for test 4

10000

Input for test 5

137 199
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61
1 62
1 63
1 64
1 65
1 66
1 67
1 68
1 69
1 70
1 71
1 72
1 73
1 74
1 75
1 76
1 77
1 78
1 79
1 80
1 81
1 82
1 83
1 84
1 85
1 86
1 87
1 88
1 89
1 90
1 91
1 92
1 93
1 94
1 95
1 96
1 97
1 98
1 99
1 100
1 101
1 102
1 103
1 104
1 105
1 106
1 107
1 108
1 109
1 110
1 111
1 112
1 113
1 114
1 115
1 116
1 117
1 118
1 119
1 120
1 121
1 122
1 123
1 124
1 125
1 126
1 127
1 128
1 129
1 130
1 131
1 132
1 133
1 134
1 135
1 136
1 137
1 138
1 139
1 140
1 141
1 142
1 143
1 144
1 145
1 146
1 147
1 148
1 149
1 150
1 151
1 152
1 153
1 154
1 155
1 156
1 157
1 158
1 159
1 160
1 161
1 162
1 163
1 164
1 165
1 166
1 167
1 168
1 169
1 170
1 171
1 172
1 173
1 174
1 175
1 176
1 177
1 178
1 179
1 180
1 181
1 182
1 183
1 184
1 185
1 186
1 187
1 188
1 189
1 190
1 191
1 192
1 193
1 194
1 195
1 196
1 197
1 198
1 199
1 200

Output for test 5

137

Input for test 6

137 200
1 3141
2 3141
3 3141
4 3141
5 3141
6 3141
7 3141
8 3141
9 3141
10 3141
11 3141
12 3141
13 3141
14 3141
15 3141
16 3141
17 3141
18 3141
19 3141
20 3141
21 3141
22 3141
23 3141
24 3141
25 3141
26 3141
27 3141
28 3141
29 3141
30 3141
31 3141
32 3141
33 3141
34 3141
35 3141
36 3141
37 3141
38 3141
39 3141
40 3141
41 3141
42 3141
43 3141
44 3141
45 3141
46 3141
47 3141
48 3141
49 3141
50 3141
51 3141
52 3141
53 3141
54 3141
55 3141
56 3141
57 3141
58 3141
59 3141
60 3141
61 3141
62 3141
63 3141
64 3141
65 3141
66 3141
67 3141
68 3141
69 3141
70 3141
71 3141
72 3141
73 3141
74 3141
75 3141
76 3141
77 3141
78 3141
79 3141
80 3141
81 3141
82 3141
83 3141
84 3141
85 3141
86 3141
87 3141
88 3141
89 3141
90 3141
91 3141
92 3141
93 3141
94 3141
95 3141
96 3141
97 3141
98 3141
99 3141
100 3141
101 3141
102 3141
103 3141
104 3141
105 3141
106 3141
107 3141
108 3141
109 3141
110 3141
111 3141
112 3141
113 3141
114 3141
115 3141
116 3141
117 3141
118 3141
119 3141
120 3141
121 3141
122 3141
123 3141
124 3141
125 3141
126 3141
127 3141
128 3141
129 3141
130 3141
131 3141
132 3141
133 3141
134 3141
135 3141
136 3141
137 3141
138 3141
139 3141
140 3141
141 3141
142 3141
143 3141
144 3141
145 3141
146 3141
147 3141
148 3141
149 3141
150 3141
151 3141
152 3141
153 3141
154 3141
155 3141
156 3141
157 3141
158 3141
159 3141
160 3141
161 3141
162 3141
163 3141
164 3141
165 3141
166 3141
167 3141
168 3141
169 3141
170 3141
171 3141
172 3141
173 3141
174 3141
175 3141
176 3141
177 3141
178 3141
179 3141
180 3141
181 3141
182 3141
183 3141
184 3141
185 3141
186 3141
187 3141
188 3141
189 3141
190 3141
191 3141
192 3141
193 3141
194 3141
195 3141
196 3141
197 3141
198 3141
199 3141
200 3141

Output for test 6

137

Input for test 7

1 200
1 33
71 6621
114 7189
101 6350
101 7120
116 7930
105 9046
110 2619
103 7834
115 6383
32 5300
77 9343
114 6530
46 1260
32 5520
75 115
111 1165
108 348
115 8316
116 9886
97 8154
100 5294
33 8905
1 55
2718 9507
5629 1706
1857 3093
4306 7201
2340 8427
2546 4250
5005 9026
9508 5480
7131 5295
3805 470
7816 5888
7633 3005
4086 7459
6702 2515
7335 5057
1005 8449
1520 3450
6483 9123
7201 2437
369 3460
5027 3221
7552 3614
9905 4652
3235 3946
2499 6948
9274 1065
8148 638
866 6189
8517 2065
4178 4095
7632 5992
8516 8242
9194 5553
2876 3830
4596 9950
2099 5595
2792 8662
3135 5049
1459 5196
4608 8953
9777 4236
170 2228
3050 8833
7259 1090
8365 2591
1467 6306
4064 8799
3634 9217
8066 513
2227 313
5642 3762
9861 9098
4261 9334
6849 5720
5244 6117
292 7202
1406 2313
7803 348
9376 7068
6047 7600
1120 8540
5697 2979
3121 9998
3307 1024
4111 478
3385 9439
3947 3329
9302 4532
1660 4905
2550 9848
9785 6901
6571 1566
3209 2488
3366 6984
2999 6523
252 3811
1515 9530
6549 1250
2525 9811
8915 8282
5746 6527
2410 8622
6226 2684
6769 5280
5958 2084
3339 4117
4264 9946
3952 5490
9430 7474
4592 4832
2188 5290
2043 7372
514 6656
3202 3402
9346 5745
3946 9217
836 8939
6363 4844
4217 3090
352 4960
3439 1975
2096 6433
980 1104
1977 5480
6032 3144
1108 2221
6648 121
6749 5575
9649 8256
6876 3716
8842 5340
4545 2418
4631 5897
1864 4839
5859 4571
6011 8020
1641 7476
7304 6552
3741 8554
9897 4213
9954 6998
7258 2248
8427 1163
6792 3678
7172 612
5275 84
3765 7583
493 9180
6659 1374
5553 5797
2344 8430
3683 1062
5106 9212
441 3914
8044 2495
1605 1295
2855 3408
2686 3054
172 3304
5961 869
3881 5114
3907 7122
9116 5001
1419 6174
647 362
432 1975
2562 1202
8778 9152
1454 9848
3875 128
9460 6411
2108 5490
4350 353
6597 4519
6218 3346
1985 4865
2207 4087
1537 5950
5843 1112
3330 7364
8104 6482
1829 7893
6156 8515
4288 601
8852 9977
8061 6597
7598 4036
2091 2758
7176 1214
103 4080
4660 8973
2926 7792
9815 1719
5977 6526
7480 3099
5416 429

Output for test 7

1

Input for test 8

10 200
6200 3528
5067 5607
2330 5146
3688 502
137 9263
8475 7783
293 5420
5651 1771
9068 6909
9213 1621
5576 3052
3059 5445
5212 1301
6486 376
5019 4563
8654 5449
8043 7141
2766 6968
6373 5497
3324 2892
2114 4001
4449 2370
3139 7642
5159 3999
5897 2393
9615 5672
1001 4133
9635 5360
2507 567
680 5256
8201 9819
5557 6968
3370 9068
6274 7654
3146 6752
9933 2029
167 221
9759 3080
2635 5015
5094 1379
8721 2722
1479 4368
3162 7209
3042 9475
869 7284
8039 9129
5955 883
5293 8410
6833 7899
4696 3269
3630 6948
1268 6164
1130 4679
6298 7727
2646 3685
4666 5402
9595 8504
8112 9280
1106 5342
5215 9506
3806 4689
342 538
5870 1527
2667 3277
1837 2797
9189 3923
6437 8576
989 6745
1061 2341
2889 9308
5608 6952
3329 1857
9580 9626
3328 5272
8523 9308
2504 3489
7698 9261
2549 9455
2391 2347
7539 8166
9846 4983
8748 4399
8913 1824
4080 6160
389 8339
8223 1407
237 4153
5381 5228
3787 506
8109 6472
7124 9920
1025 7147
779 2081
9741 9125
4937 4351
2505 1406
7405 8005
3993 7171
9049 7237
8399 3970
3002 9971
8059 7708
6313 202
6960 2827
6603 6633
7774 7588
3351 2271
657 6224
8585 2722
829 4501
5593 5710
5445 3924
5838 1796
3973 3272
3225 2792
7361 6607
4285 3743
1681 615
1524 800
411 3640
2124 7398
4658 5582
3396 6889
2663 4807
831 688
4009 2283
1366 6671
1966 7333
8653 5531
964 6018
4764 381
8751 5554
3102 2441
2612 3956
5389 8309
1039 6912
4778 211
1295 6687
1544 2805
5947 4612
4743 9378
8983 7559
6018 7638
2720 4255
1637 4257
8289 2576
8315 6718
4671 9002
2721 7257
8586 4812
5247 3283
1253 5446
5145 913
9112 3784
6841 7538
6942 257
9835 7607
933 2049
6466 5415
608 5860
650 4326
6141 8393
5052 3647
7626 1978
5688 9937
5778 9425
9320 6671
7080 8645
5971 5467
7631 9125
3075 8990
8133 5505
9123 3649
1259 8947
8752 2609
2868 1640
2111 2608
407 9467
3688 2879
7731 9960
7641 9978
2293 8225
1841 7681
2069 262
3378 7950
9175 7411
7083 4259
212 5489
1795 6831
66 9369
8586 5207
3043 6405
1182 4502
9509 7480
2323 129
6062 956
5079 1865
5910 4945
5256 2309
3580 5891

Output for test 8

1256

Input for test 9

60 350
3456 5306
8668 3235
22 3871
5361 2153
4378 2757
9483 5928
1130 3119
6858 7621
3410 9301
2479 4456
1814 2876
8914 6817
2272 1373
7810 7943
3637 6567
8224 1537
4771 7092
962 6891
9044 1144
3901 2674
8601 9773
9244 3383
7356 6082
1734 2453
6908 765
3640 4212
7380 5074
6446 2553
6847 9652
2570 4256
2144 483
3926 793
4035 3266
4409 1239
3913 9430
5555 8309
8044 8865
4947 1150
3602 5399
6163 3032
7244 510
5583 6154
5058 975
6978 8380
8987 8257
8739 9547
6691 1130
4395 9017
255 7078
6507 8804
3464 4167
9384 8413
9562 1507
3257 4330
3713 3164
25 9419
1924 956
8283 1959
338 6982
5238 5260
4807 9325
6806 328
9344 7849
4926 7553
2708 5951
117 7785
6197 6171
4030 5852
181 2111
1626 7286
3057 246
7553 1650
9960 4980
8313 5835
1095 297
5973 3550
230 2253
101 2779
6683 9573
5523 1379
5515 9390
1912 1992
7843 1711
173 5941
9579 4376
973 1798
9799 8987
3966 8525
4360 9758
55 8631
2180 1806
4058 2379
1509 8761
8334 510
8240 8191
7580 208
8551 3754
1817 9492
1784 2746
3473 1989
139 7714
6700 4445
2969 9937
9695 7018
5648 7328
9133 6101
4831 4179
2940 9542
6404 6340
4530 7625
7832 4643
4749 8462
4305 2735
5480 6565
4905 6088
154 8952
3396 5043
1332 6853
3870 2716
44 7378
3478 9517
48 5528
1422 4660
999 2987
611 4177
8819 1881
342 4794
7528 9919
6483 998
3437 9359
8310 7740
2782 3590
443 8057
773 4113
1490 4312
181 7168
9047 1319
5979 6580
9566 6820
996 3329
5209 6528
7673 6167
6085 1902
2899 1553
911 8920
6659 6336
6277 5573
3629 9440
9905 6719
7383 753
4272 7746
5417 3915
494 9671
6490 7747
1075 6411
2938 3838
4 2636
4537 610
8514 6088
1359 7436
123 9425
4997 8017
3809 6399
9470 4977
2082 65
7810 6852
766 6353
2375 9578
3676 7611
4021 8865
2702 4751
3738 6958
3919 9057
1496 8274
2061 2433
8209 2855
871 8535
4934 3205
4533 4679
1095 755
7606 6614
9319 5257
4834 4723
2333 1693
6909 8510
9612 6353
9662 5962
5018 3349
7974 9932
8716 6514
5720 35
4921 6924
6480 6590
7621 6206
6960 7365
3978 8715
3971 4565
5639 9648
7693 5157
18 7971
675 4601
6915 5981
5681 6688
2972 1932
4797 6
40 1687
4963 516
3458 1313
7518 1442
5158 7430
2496 4478
5394 9136
5135 2819
7975 1033
5355 2827
3780 4344
6676 2382
9069 694
8977 2356
2361 2040
79 126
641 8753
65 5041
2834 450
7879 7582
8411 7992
3479 375
3193 3805
4837 8613
1440 7519
8214 6543
8924 1571
2264 4889
3596 7993
6384 1240
7717 5956
1060 6462
7854 8358
5159 7476
1410 688
5031 3038
9764 9820
3624 8509
7121 9308
3178 4812
1355 4912
2834 1391
2631 278
4622 5097
2689 6226
8533 7358
171 405
5114 5945
3420 8025
5064 273
9662 1181
1001 94
4954 5777
1436 976
2140 8426
9690 4613
2355 3494
123 2523
7620 4985
7562 1097
4806 6660
3416 6094
8390 4976
9352 8530
5154 1810
9342 767
7212 1167
6943 342
7670 2165
591 8378
9342 6161
6006 280
2802 1696
6680 2480
3576 6773
9784 593
3038 8381
9709 3200
8081 1428
3237 5412
6179 3234
752 8930
5624 3390
5555 7694
2423 3293
9453 2497
9128 1764
3459 1810
4289 8281
5054 6490
7082 7865
2597 1189
4388 119
7898 8657
4069 8820
8405 7486
6416 247
3636 9156
6849 2039
5331 5542
8038 5623
7386 1135
9296 7165
5446 7196
37 3584
7800 6851
8039 3470
9941 397
5405 8779
7598 7838
5324 9473
6071 6003
1510 1739
3777 9707
1600 8359
3981 5459
2945 9638
3154 7719
4914 2240
5823 4951
1801 4951
8420 3623
371 6192
1322 4712
2550 5775
5248 5271
7625 7873
9611 7670
7376 9135
7493 3387
8845 8976
4965 7825
1895 8141
380 4470
9421 3161
4463 6202
6176 1221
3764 9234
3946 6546
8673 5085
356 6495
4367 272
7941 4332
3466 3977
3715 5317

Output for test 9

3449

Input for test 10

457 500
9423 9789
419 9613
9563 9164
9856 902
9965 9014
9339 543
532 645
9040 9412
9812 9614
9174 9056
115 9275
9975 9810
249 790
620 9328
855 9189
123 9296
9449 623
9137 994
700 9411
51 9159
308 561
963 9868
255 9018
696 40
129 9673
933 9678
9256 9940
43 9556
9469 9020
9706 14
409 277
9614 54
9319 860
9595 9051
9556 9353
263 188
9199 9657
9368 996
409 9505
9709 663
9720 9062
55 9813
601 9016
280 9288
44 9473
9885 68
146 672
9186 9238
855 133
293 759
156 460
618 9782
579 9961
9381 570
725 554
926 9015
9280 9609
438 9392
244 9270
9410 578
46 9434
428 9867
729 43
9294 9215
146 495
679 880
9478 9162
559 986
9615 9380
39 9684
144 9228
9262 9021
9563 9182
9072 9259
307 9382
348 9828
507 250
9751 9985
629 9054
9304 9750
400 954
9883 482
979 9008
9945 763
9340 9190
9720 7
9387 277
230 149
300 9341
501 841
241 9845
9299 9440
633 9025
9803 9178
638 825
9672 848
9870 9956
648 109
9579 9114
9115 9811
9830 431
9150 882
9946 707
9618 363
62 495
348 653
571 596
9663 325
9347 9774
9937 343
167 9795
956 9235
679 9220
9786 498
324 9409
582 9480
375 90
207 261
186 9375
385 861
650 792
9575 9001
735 761
9790 551
380 9274
9577 663
452 9900
678 251
306 895
684 9522
9164 733
872 335
627 9461
9601 9638
9160 40
9873 9452
36 515
688 488
9418 922
9442 56
670 9062
501 624
9886 211
9992 378
9448 9534
236 9885
878 9377
998 9676
979 439
915 820
9924 975
789 481
9405 934
9749 2
9563 622
304 9548
9792 9888
306 9497
9687 171
535 796
9052 313
9872 9616
939 9648
9049 9773
9248 9015
9378 9858
672 391
9686 9314
618 9834
9984 16
557 901
9771 9630
9478 9258
197 785
9451 425
9937 9522
815 483
547 9863
570 9687
221 9869
40 9762
9890 9193
9451 9126
9954 350
701 9957
9671 54
274 9951
9598 588
9594 9619
201 528
772 9933
811 31
249 9539
9043 9821
587 76
762 135
9160 9613
56 143
372 9652
9022 9956
157 9493
725 49
268 652
139 9749
653 372
9744 9763
9573 810
9979 9665
9938 996
9768 98
9480 232
886 990
9528 597
578 61
477 9887
9574 27
995 276
9230 9922
178 653
9856 9048
9295 9599
9913 9657
9318 9588
258 598
517 184
302 9072
9725 9106
927 94
748 972
957 102
124 9901
9992 338
273 164
486 9243
9624 9115
9503 640
9176 784
277 9229
103 134
919 988
695 821
9407 9356
581 9023
212 28
579 169
400 9394
162 9036
9735 9674
9547 844
9924 9631
722 87
315 9032
277 9550
9572 9471
853 22
150 9571
9154 3
465 9070
9579 9531
9518 332
280 9862
9106 9351
9487 9783
9278 619
624 843
9657 9376
143 9149
884 88
668 9778
245 9339
247 126
9772 9111
9285 291
210 175
9640 9321
9737 111
344 197
908 9950
440 9525
271 224
9552 396
9220 9640
651 89
9490 196
235 147
9399 1000
9925 62
9809 683
9850 9351
9298 9873
106 9383
118 823
9444 198
869 552
9329 641
601 206
9897 739
9432 9491
9567 642
939 9394
9865 9995
9001 299
873 237
965 928
9352 9776
884 9406
212 9430
404 350
332 543
9386 706
132 311
9264 868
608 9343
178 9842
191 9758
9743 9516
9703 273
9430 9251
9729 502
9998 97
9189 9900
709 82
692 9156
9085 891
707 829
492 9670
9011 9526
9449 954
28 9297
9633 635
9893 361
159 292
765 9508
9304 723
358 9619
120 624
9557 235
9890 871
9950 297
185 9576
707 9741
796 145
9469 414
565 150
363 820
605 9254
9025 216
9371 812
9387 794
405 914
9184 9062
364 9612
824 9098
953 436
9958 439
9006 9290
9328 369
795 9636
609 343
742 9598
9358 698
9343 523
9514 9925
9438 9208
994 16
9206 9899
386 79
528 396
9159 117
577 9099
9696 249
467 158
9447 952
9097 102
497 767
9636 898
9394 9593
9644 9698
638 584
9058 268
9736 195
9378 808
9820 9154
440 9546
110 9715
9478 9170
138 9385
9847 928
9548 9064
9879 9454
9980 903
489 859
9079 9234
83 957
9639 9998
159 9365
756 9963
19 9118
9968 852
845 9179
9444 9791
889 9791
9559 9180
9155 9087
732 9820
9410 141
551 9506
405 9840
608 9698
9409 9552
76 336
77 873
9449 909
468 9884
9256 9236
9370 166
9651 789
980 9676
210 9322
9092 445
9045 9695
107 144
386 9945
9113 9043
9959 9471
687 780
514 9467
9640 586
9613 90
9336 48
9156 9231
9972 673
9825 442
57 111
9970 9305
326 58
875 558
9918 9060
765 9286
788 862
9412 178
876 9082
9718 9353
950 673
9446 715
892 9381
9284 9201
720 172
315 657
9013 447
9109 9419
502 17
9460 397
9911 9562
349 9634
9751 9273
9763 106
311 9451
702 9254
90 611
9803 413
374 797
9209 493
700 956
309 217
317 173
9399 9429
386 9329
892 9131
638 9311
829 821
9894 9480
541 33
207 9423
9172 850
9966 149
9341 9458
387 9572
118 447
9624 638
407 477
9069 9228
9447 325
9802 866
194 9142
695 9854
536 36
9738 9469
9953 9014
413 90
85 9743
9410 846
9415 9637
991 93
455 9507
9496 9262
9616 882
9166 468
9264 259
552 9539

Output for test 10

9880