===INPUT===
500 1512
77 55 86 58 70 98 7 52 38 90 53 66 94 52 26 100 45 37 5 100 21 52 67 87 83 71 67 80 87 29 39 16 13 16 57 75 22 76 36 41 61 40 46 12 59 71 45 5 93 50 93 97 6 76 82 98 20 13 27 59 67 16 50 20 99 18 96 77 69 4 55 56 37 77 22 33 90 55 77 78 75 12 66 59 29 18 67 36 57 23 45 9 99 90 72 13 31 30 56 37 23 14 100 91 49 1 45 62 47 39 61 48 96 43 27 35 32 50 62 93 70 95 90 58 29 17 43 46 18 86 57 51 53 18 22 39 30 8 14 22 52 46 60 19 98 59 18 1 50 92 66 36 48 95 98 59 60 8 85 44 47 88 23 38 25 44 63 75 90 26 70 94 27 46 91 70 12 80 77 88 12 48 29 77 22 17 72 88 25 23 75 70 46 67 81 7 34 36 17 76 16 19 85 14 83 90 90 18 35 18 53 52 40 2 53 29 36 23 90 8 51 73 73 97 60 54 29 29 33 54 61 97 41 47 35 77 61 46 77 22 53 89 58 38 24 22 27 52 11 40 94 44 26 16 63 73 39 47 65 93 40 74 95 64 43 34 68 67 100 98 95 15 57 73 11 86 76 92 95 73 14 92 69 43 3 95 44 13 86 77 94 83 66 53 39 77 77 9 31 93 60 78 6 72 51 83 2 55 39 9 52 33 89 71 31 42 56 30 5 50 42 4 88 70 83 97 32 13 75 58 13 91 69 66 24 38 84 61 21 62 81 87 80 75 24 33 100 5 95 98 90 47 61 56 22 86 28 27 31 52 18 75 71 16 48 26 50 5 51 53 61 19 2 23 49 20 24 2 35 47 20 49 23 81 78 93 78 84 60 84 17 85 29 78 94 49 44 38 72 64 88 1 54 57 63 98 44 59 64 98 97 48 94 56 88 35 70 39 2 44 39 18 19 9 8 25 13 61 70 31 97 87 16 47 100 32 83 70 77 61 37 77 83 73 73 3 17 66 24 54 47 65 82 67 24 27 68 66 59 49 60 79 87 83 58 30 2 93 46 85 7 34 78 55 26 82 77 95 97 69 76 26 69 76 36 14 3 84 68 23 35 33 84 43 20 72 58 57 1 44
1 99
1 249
1 80
1 276
1 66
1 228
1 23
1 279
1 335
1 204
1 48
1 207
1 346
1 478
1 226
1 469
1 247
1 119
1 441
1 106
1 277
1 237
1 211
1 402
1 76
1 434
1 256
1 140
1 167
1 5
1 359
1 193
1 341
1 97
1 442
1 451
1 416
1 380
1 336
1 64
1 399
1 443
1 12
1 271
1 201
1 415
1 495
1 122
1 28
1 157
1 174
1 212
1 329
1 417
1 448
1 93
1 121
1 151
1 40
1 497
1 47
1 36
1 263
1 8
1 459
1 57
1 27
1 18
1 222
1 413
1 214
1 34
1 264
1 244
1 62
1 16
1 11
1 116
1 235
1 73
1 169
1 120
1 354
1 477
1 230
1 461
1 265
1 136
1 213
1 281
1 352
1 273
1 84
1 196
1 460
1 41
1 105
1 379
1 179
1 411
1 305
1 353
1 200
1 192
1 71
1 479
1 321
1 243
1 227
1 113
1 429
1 375
1 43
1 300
1 54
1 363
1 205
1 377
1 74
1 83
1 53
1 433
1 104
1 115
1 58
1 457
1 313
1 133
1 475
1 125
1 152
1 351
1 299
1 129
1 258
1 195
1 25
1 178
1 7
1 484
1 107
1 232
1 234
1 389
1 358
1 221
1 216
1 431
1 150
1 86
1 29
1 184
1 102
1 292
1 160
1 365
1 463
1 259
1 376
1 332
1 251
1 109
1 425
1 252
1 406
1 357
1 285
1 238
1 79
1 33
1 345
1 61
1 275
1 317
1 161
1 46
1 44
1 3
1 56
1 272
1 444
1 90
1 489
1 423
1 344
1 318
1 307
1 209
1 246
1 262
1 261
1 301
1 488
1 144
1 166
1 170
1 387
1 114
1 420
1 430
1 189
1 268
1 175
1 407
1 42
1 378
1 81
1 343
1 199
1 418
1 400
1 324
1 100
1 51
1 392
1 138
1 294
1 435
1 203
1 220
1 410
1 191
1 26
1 185
1 472
1 69
1 295
1 254
1 426
1 327
1 156
1 388
1 137
1 130
1 270
1 339
1 342
1 146
1 229
1 468
1 91
1 398
1 385
1 132
1 473
1 369
1 436
1 298
1 94
1 15
1 315
1 266
1 197
1 322
1 462
1 482
1 437
1 78
1 405
1 287
1 386
1 337
1 124
1 188
1 291
1 35
1 181
1 39
1 421
1 59
1 177
1 217
1 154
1 30
1 330
1 127
1 218
1 465
1 123
1 280
1 153
1 67
1 304
1 219
1 134
1 19
1 55
1 32
1 98
1 370
1 394
1 31
1 432
1 112
1 194
1 6
1 438
1 248
1 496
1 422
1 306
1 68
1 128
1 50
1 323
1 22
1 187
1 236
1 108
1 331
1 245
1 223
1 183
1 110
1 303
1 286
1 159
1 87
1 452
1 241
1 269
1 470
1 368
1 428
1 381
1 139
1 485
1 88
1 297
1 493
1 135
1 367
1 20
1 480
1 372
1 319
1 340
1 412
1 316
1 163
1 289
1 126
1 24
1 274
1 145
1 9
1 173
1 455
1 404
1 348
1 143
1 328
1 334
1 176
1 310
1 414
1 483
1 85
1 390
1 456
1 288
1 355
1 149
1 401
1 446
1 180
1 117
1 4
1 458
1 82
1 215
1 255
1 498
1 75
1 466
1 168
1 349
1 453
1 240
1 103
1 52
1 464
1 198
1 253
1 471
1 186
1 70
1 96
1 250
1 362
1 360
1 449
1 440
1 487
1 350
1 171
1 361
1 500
1 202
1 447
1 92
1 190
1 142
1 397
1 37
1 486
1 347
1 312
1 131
1 494
1 383
1 141
1 60
1 101
1 118
1 371
1 2
1 314
1 408
1 147
1 403
1 231
1 476
1 278
1 162
1 13
1 155
1 172
1 206
1 373
1 239
1 490
1 396
1 333
1 210
1 419
1 366
1 182
1 225
1 325
1 374
1 491
1 454
1 393
1 450
1 492
1 308
1 499
1 395
1 309
1 224
1 65
1 424
1 326
1 63
1 302
1 356
1 282
1 481
1 233
1 89
1 45
1 439
1 474
1 338
1 384
1 311
1 409
1 165
1 284
1 72
1 38
1 427
1 148
1 21
1 208
1 391
1 267
1 95
1 242
1 290
1 283
1 111
1 364
1 164
1 257
1 260
1 293
1 77
1 14
1 296
1 467
1 49
1 320
1 382
1 445
1 158
1 17
1 10
2 458
2 210
2 73
2 35
2 181
2 415
2 248
2 304
2 83
2 396
2 141
2 308
2 10
2 56
2 202
2 374
2 37
2 161
2 170
2 283
2 58
2 489
2 295
2 427
2 428
2 277
2 340
2 495
2 236
2 135
2 390
2 68
2 229
2 43
2 247
2 381
2 418
2 258
2 379
2 201
2 48
2 185
2 7
2 421
2 111
2 325
2 386
2 8
2 365
2 57
2 414
2 85
2 448
2 368
2 71
2 31
2 315
2 25
2 298
2 239
2 370
2 406
2 459
2 147
2 487
2 36
2 29
2 183
2 251
2 208
2 383
2 440
2 422
2 63
2 91
2 343
2 449
2 271
2 480
2 122
2 337
2 234
2 335
2 334
2 355
2 417
2 372
2 62
2 424
2 228
2 294
2 450
2 328
2 40
2 456
2 65
2 451
2 127
2 429
2 307
2 97
2 404
2 435
3 261
3 189
3 123
3 164
3 345
3 254
3 247
3 415
3 477
3 343
3 56
3 27
3 163
3 203
3 58
3 262
3 242
3 284
3 187
3 229
3 171
3 132
3 375
3 167
3 136
3 63
3 494
3 33
3 492
3 487
3 362
3 453
3 456
3 457
3 287
3 290
3 340
3 311
3 111
3 255
3 279
3 15
3 445
3 73
3 353
3 31
3 479
3 431
3 210
3 105
3 199
3 47
3 209
3 81
3 188
3 71
3 358
3 180
3 296
3 339
3 96
3 490
3 405
3 16
3 302
3 434
3 326
3 294
3 285
3 391
3 286
3 133
3 198
3 149
3 357
3 266
3 327
3 147
3 283
3 74
3 205
3 120
3 435
3 65
3 380
3 129
3 291
3 68
3 92
3 278
3 421
3 373
3 69
3 70
3 159
3 374
3 224
3 144
3 306
3 190
3 30
3 281
3 127
3 245
3 239
3 211
3 4
3 227
3 299
3 312
3 179
3 202
3 138
3 336
3 464
3 7
3 161
3 449
3 355
3 274
3 344
3 35
3 9
3 11
3 134
3 48
3 173
3 142
3 378
3 76
3 379
3 174
3 215
3 25
3 381
3 470
3 293
3 41
3 461
3 146
3 324
3 334
3 376
3 55
3 232
3 26
4 210
4 299
4 468
4 9
4 98
4 193
4 46
4 93
4 284
4 77
4 68
4 37
4 398
4 390
4 463
4 288
4 341
4 219
4 31
4 308
4 368
4 457
4 50
4 49
4 66
4 86
4 36
4 91
4 114
4 24
4 209
4 90
4 214
4 322
4 448
4 258
4 110
4 278
4 67
4 216
4 70
4 108
4 345
4 300
4 38
4 10
4 234
4 84
4 498
4 474
4 207
4 388
4 301
4 478
4 192
4 23
4 377
4 293
4 17
4 415
4 88
4 240
4 113
4 408
4 166
4 174
4 494
4 53
4 163
4 162
4 128
4 177
4 405
4 254
4 495
4 96
4 137
4 247
4 237
4 317
4 452
4 239
4 396
4 227
4 375
4 40
4 151
4 372
4 187
4 63
4 439
4 355
4 233
4 450
4 445
4 289
4 105
4 400
4 462
4 79
4 267
4 435
4 369
4 26
4 467
4 204
4 71
4 30
4 202
4 130
4 444
4 382
4 94
5 128
5 438
5 94
5 58
5 405
5 339
5 185
5 142
5 316
5 340
5 262
5 125
5 68
5 318
5 462
5 328
6 212
6 44
6 124
6 112
6 152
6 177
6 156
6 154
6 432
6 353
6 235
6 340
6 271
6 374
6 479
6 444
6 183
6 113
6 126
6 205
6 15
6 447
6 250
6 111
6 303
6 18
6 209
6 499
6 57
6 434
6 318
6 60
6 157
6 184
6 342
6 24
6 455
6 261
6 95
6 100
6 354
6 31
6 128
6 446
6 108
6 399
6 437
6 238
6 274
6 142
6 206
6 129
6 74
6 327
6 406
6 456
6 16
6 151
6 470
6 204
6 326
6 225
6 73
6 248
6 39
6 64
6 302
6 199
6 90
6 339
6 404
6 12
6 241
6 412
6 43
6 48
6 63
6 266
6 352
6 343
6 94
6 478
6 309
6 19
6 294
6 258
6 160
6 83
6 233
6 361
6 179
6 400
6 357
6 79
6 254
6 341
6 232
6 170
6 153
6 458
6 462
6 396
6 158
6 101
6 119
6 264
6 109
6 45
6 293
6 251
6 41
6 372
6 171
7 147
7 63
7 180
7 238
7 329
7 316
7 282
7 206
7 341
7 318
7 304
7 483
7 460
7 37
7 272
7 320
7 324
8 425
8 242
8 323
8 24
8 389
8 181
8 458
8 96
8 203
8 490
8 320
8 73
9 423
9 367
9 386
10 430
11 359
12 303
13 244
14 436
15 404
16 65
17 123
18 417
19 392
20 35
21 284
22 480
23 270
24 222
25 140
26 87
27 138
28 242
29 469
30 294
31 64
32 374
33 393
34 353
35 338
36 336
37 45
38 58
39 406
40 295
41 125
42 275
43 56
44 446
45 205
46 102
47 146
48 363
49 288
50 65
51 245
52 240
53 178
54 404
55 85
56 264
57 273
58 451
59 212
60 357
61 216
62 81
63 101
64 272
65 246
66 148
67 309
68 338
69 376
70 296
71 248
72 126
73 97
74 380
75 283
76 430
77 150
78 304
79 289
80 247
81 84
82 442
83 238
84 391
85 208
86 109
87 312
88 365
89 220
90 451
91 197
92 116
93 462
94 179
95 212
96 492
97 402
98 372
99 186
100 257
101 288
102 186
103 403
104 120
105 305
106 116
107 177
108 167
109 403
110 410
111 276
112 180
113 263
114 384
115 410
116 241
117 358
118 301
119 386
120 306
121 307
122 438
123 391
124 431
125 315
126 265
127 131
128 480
129 348
130 388
131 461
132 263
133 497
134 190
135 384
136 369
137 350
138 202
139 347
140 271
141 306
142 458
143 461
144 426
145 474
146 169
147 371
148 437
149 312
150 320
151 344
152 302
153 495
154 382
155 480
156 263
157 424
158 254
159 284
160 270
161 469
162 399
163 193
164 427
165 189
166 454
167 399
168 281
169 460
170 443
171 370
172 192
173 238
174 272
175 373
176 226
177 231
178 248
179 477
180 347
181 245
182 472
183 493
184 229
185 435
186 429
187 331
188 459
189 407
190 344
191 419
192 265
193 355
194 382
195 491
196 325
197 365
198 307
199 469
200 449
201 404
202 232
203 250
204 257
205 352
206 440
207 228
208 422
209 440
210 383
211 449
212 236
213 402
214 344
215 388
216 259
217 302
218 398
219 230
220 292
221 394
222 241
223 235
224 438
225 411
226 396
227 359
228 414
229 268
230 407
231 287
232 492
233 286
234 307
235 273
236 251
237 381
238 242
239 355
240 457
241 283
242 370
243 406
244 366
245 354
246 251
247 300
248 349
249 407
250 287
251 404
252 440
253 412
254 263
255 450
256 268
257 421
258 334
259 434
260 333
261 490
262 315
263 369
264 491
265 347
266 492
267 355
268 397
269 322
270 322
271 465
272 496
273 294
274 388
275 322
276 492
277 477
278 479
279 318
280 490
281 461
282 491
283 446
284 433
285 426
286 455
287 410
288 439
289 471
290 435
291 430
292 315
293 478
294 315
295 473
296 360
297 326
298 430
299 459
300 319
301 362
302 457
303 440
304 329
305 455
306 480
307 338
308 491
309 376
310 406
311 477
312 391
313 393
314 354
315 407
316 463
317 386
318 367
319 414
320 395
321 429
322 332
323 492
324 334
325 468
326 459
327 439
328 353
329 460
330 413
331 451
332 474
333 371
334 398
335 433
336 383
337 417
338 408
339 385
340 405
341 402
342 346
343 399
344 418
345 416
346 358
347 369
348 393
349 465
350 417
351 500
352 477
353 382
354 479
355 365
356 432
357 437
358 446
359 376
360 366
361 377
362 435
363 409
364 460
365 385
366 383
367 387
368 382
369 480
370 422
371 440
372 401
373 402
374 424
375 484
376 401
377 425
378 400
379 460
380 391
381 403
382 446
383 417
384 444
385 488
386 466
387 456
388 457
389 410
390 462
391 423
392 409
393 423
394 483
395 433
396 464
397 406
398 410
399 426
400 407
401 432
402 430
403 448
404 488
405 468
406 479
407 442
408 448
409 412
410 440
411 434
412 473
413 487
414 451
415 487
416 421
417 497
418 431
419 449
420 479
421 485
422 472
423 493
424 428
425 484
426 429
427 429
428 483
429 483
430 500
431 442
432 449
433 493
434 496
435 462
436 480
437 443
438 500
439 473
440 441
441 456
442 484
443 453
444 471
445 449
446 488
447 448
448 470
449 499
450 477
451 458
452 492
453 468
454 484
455 471
456 459
457 485
458 463
459 485
460 487
461 466
462 473
463 493
464 477
465 489
466 479
467 470
468 484
469 496
470 496
471 491
472 482
473 478
474 500
475 499
476 490
477 481
478 479
479 485
480 497
481 485
482 497
483 492
484 487
485 494
486 500
487 498
488 500
489 492
490 500
491 495
492 499
493 497
494 495
495 500
496 497
497 500
498 500
499 500
===OUTPUT===
948
===END===