King's tour with capturing the pawns

Hi everyone,
I have a problem with the following task:
On a chessboard N x N M white pawns were placed. The black king is at (0,0) (upper left corner) and has to reach (n-1,n-1)(lower right corner). During his tour, the king must capture all the pawns.
The case of check can be ignored. What is the minimum of King’s moves?


Time limit: 10sec.
Memory limit: 60MB

N - length of side of chessboard
M - number of pawns
Then M coordinates of pawns

e.g. For input:
0 3
2 1
3 7
4 0
4 2
4 6
7 2
7 3
6 7
5 5

Output is:

It seems to be a problem of traveling salesman but i think it can be solved much faster. I was thinking about something similar to Kruskal. I would be grateful if anyone solved/gave hint to solve this problem.