88

Color the board like a chessboard. Imagine this as a walk around the chessboard. The last unit square we visit on the diagonal, we have gone over at least $39$ other unit squares before this point (since we can't go back to the other side any more now and we've visited 12+7 black and 19 white cells + the one we're standing on). Notice that the numbers on the diagonal have the same parity so in our best case we would have $1+3+5+7+9+13=49$ and with the $39$ before this point = $88$. There is a relatively easy construction for it.