408910: GYM103379 F Present Drops

Recently, Santa'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, Santa 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 Santa 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, Santa can take a single step in one of the four cardinal directions or stay in place. Figure out Santa's optimal path to pick up as many presents as possible before the presents are taken and output the maximum number of presents that Santa can get.

The first line consists of $$$4$$$ integers, $$$N$$$ ($$$1 \leq N \leq 750$$$), $$$P$$$ ($$$1 \leq P \leq 1000$$$), $$$s_x$$$, $$$s_y$$$ ($$$1 \leq s_x, s_y \leq N$$$). This gives the size of the 2D square grid, number of presents that the elves will drop, and Santa's starting $$$x$$$ and $$$y$$$ coordinate, respectively. The next $$$P$$$ lines consist of three integers, $$$t_i, x_i, y_i$$$ ($$$1 \leq t_i \leq 10^6$$$), ($$$1 \leq x_i, y_i \leq N$$$), which give the time (in minutes) and location of a present drop.

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

5 3 1 1
1 1 1
6 5 5
11 1 1

2

10 5 1 1
23 10 3
13 10 1
18 9 1
28 10 7
8 1 10

4

In the first sample, Santa can collect the first present at time $$$1$$$, the second present at time $$$9$$$, but does not have time to get back to collect the final gift (which disappears at time $$$16$$$)