Colour a $20000\times 20000$ square grid using 2000 different colours with 1 colour in each square. Two squares are neighbours if they share a vertex. A path is a sequence of squares so that 2 successive squares are neighbours. Mark $k$ of the squares. For each unmarked square $x$, there is exactly 1 marked square $y$ of the same colour so that $x$ and $y$ are connected by a path of squares of the same colour. For any 2 marked squares of the same colour, any path connecting them must pass through squares of all the colours. Find the maximum value of $k$.