Логичка матрица димензије \(n\times n\) у почетку садржи све нуле. Након тога се насумично додаје једна по једна јединица. Кретање по матрици је могуће само по јединицама и то само на доле, на горе, на десно и на лево. Написати програм који учитава димензију матрице, а затим позицију једне по једне јединице и одређује након колико њих је први пут могуће сићи од врха до дна матрице (са произвољног поља прве врсте до произвољног поља последње врсте матрице).

Улаз

Са стандардног улаза се учитава димензија матрице \(1 \leq n \leq 200\), затим број поља \(m\) (\(1 \leq m \leq n^2\)) у које се уписује јединица, а затим у наредних \(m\) редова координате тих поља (број врсте и број колоне од \(0\) до \(n-1\), раздвојени размаком).

Излаз

Опис излазних података.

Пример

Улаз

4
9
0 0
0 1
1 1
3 3
1 3
2 0
3 0
2 1
2 2

Излаз

8

Објашњење

После 8 учитаних поља, матрица постаје

1100
0101
1100
1001

и врх и дно постају спојени.