Codah ClubTrain. Submit. Improve.
Sign in
English
#0000F8

z-pharaoh

Professor Z teaches history in local school. His lessons are very interesting and his student Pedja extremely loves history. Once, while professor Z was talking about ancient Egypt, Pedja was daydreaming and fell in sleep.


He dreamed that he was about to go into a pyramid and on the entrance there was a story on the wall saying that the one who enters the pyramid and is able to climb to the highest pyramid level, will become the new pharaoh. The Pyramid is square based, made of 1x1x1 cube blocks. The base (level 0) always has an odd length of (N blocks. Level one is then N-2 in length, and so on. The top of the Pyramid is made of only one block.


Due to years and years of crises (far worse that this current economic one), thief had stolen some of interior blocks (but never the exterior ones). This way, there are some halls inside the pyramid. The remaining blocks stand one on top of others, but can also float in space.

Pedja can freely move on every floor as long as there is a block he can stand on (he can move: left, right, front or back). He can also climb on a neighbor block if it is no more than one level up (and if there is some space above him). He can also jump down to a neighbor block no matter how many levels below the neighbor block is (all this is possible because this is just a dream).


The foundation (basement) below pyramid is cube NxNxN. Some of the foundation blocks have also been stolen. Good news is that the robbers left a list of the stolen blocks. First visible level of pyramid is marked with 0. Nearest left stone on the left at level 0 is (1,1,0) a diagonally opposite (N,N,0)


Image: piramida

InputIn first line of standard input is integer N, (2<N<100) length of level 0 border of pyramid.
In second row is integer B, (1<B<=100 000) number of stolen blocks.
In next B lines of standard input are three integer separated with blank space: Sx, Sy i Sz coordinates of stolen block S, (1 <= Sx, Sy <= N; -N <= Sz <= (N+1)/2).

OutputTo the first line of standard output You need to write a number that represent maximal level Pedja can climb on. He always starts from block marked with ((N+1)/2, 1, 0), half length of 0 level side. Counting of maximal reached interior level of pyramid starts after Pedja makes first step. (e.g. if after first step pedja has to move to a lower level, then the maximal level he can climb on can be lower than the initial level 0)

Input:
7
11
4 1 0
4 2 0
4 2 -1
4 2 -2
4 3 -2
3 3 -2
2 3 -2
1 3 -2
1 4 -2
4 2 -3
4 3 -3

Output:
-2
Image: example

Explanation: Immediately after first step Pedja is falling three blocks down. From there he can go one block forward and then up-left. This is possible because there is no block on (4,3,-2) to close his passage. He is on -2 level now. Further, he can move two blocks to the left and then one step forward but all of this is on same level. Since he fell down after first step counting starts from -3. This mean that -2 is maximal possible level to reach.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.