Recently, NAME_1's elves went rogue and commandeered his sleigh! Rather than dropping off presents to where they are supposed to go, the elves are randomly tossing presents off the sleigh random times.

Fortunately, through a double-agent elf, NAME_1 has determined the locations and times where the presents will be dropped. Unfortunately, the presents will be stolen by angry Canadian children (who happened to not get gifts this year) exactly 5 minutes after they are initially dropped, so NAME_1 must be quick to pick up as many presents as he can to be delivered correctly later. The elves also want to spread out their present drops over a longer period of time, so it is guaranteed that any two present drops will be at least 5 minutes apart.

You are given a 2D square grid representing the area where elves are dropping presents and a list of present drop times and coordinate locations. In one minute, NAME_1 can take a single step in one of the four cardinal directions or stay in place. Figure out NAME_1's optimal path to pick up as many presents as possible before the presents are taken and output the maximum number of presents that NAME_1 can get.

Input
The first line consists of 4
 integers, N
 (1≤N≤750
), P
 (1≤P≤1000
), sx
, sy
 (1≤sx,sy≤N
). This gives the size of the 2D square grid, number of presents that the elves will drop, and NAME_1's starting x
 and y
 coordinate, respectively. The next P
 lines consist of three integers, ti,NAME_2,yi
 (1≤ti≤106
), (1≤NAME_2,yi≤N
), which give the time (in minutes) and location of a present drop.

Output
Output a single integer giving the maximum number of presents that NAME_1 can successfully collect.

Generate complete code for the same