Let's start by exploring some cases with small ~K~ values by hand to determine which roads Loki should optimally destroy, and what the resulting maximum shortest distance will be. When ~K = 0~, no roads are destroyed, and the maximum shortest distance will be ~(N-1)+(M-1)~, for example between the top-right and bottom-left cities. When ~K = 1~, destroying a single horizontal road (for example the leftmost one in the top row) is the best that Loki can do, as it increases the answer by a whole ~N-1~ (for example, the shortest distance between the top-left and top-right cities will be ~2(N-1)+(M-1)~). When ~K = 2~, assuming that ~M > 2~, the answer can be increased by a whole additional ~N-1~ if Loki destroys one horizontal road in the top row and one in the bottom row, as long as they're not in the same column (for example, the shortest distance between the top-left city and the bottom-right city can be ~3(N-1)+(M-1)~).

This pattern continues for the first ~M-1~ roads destroyed by Loki – if he destroys horizontal roads alternating between the top and bottom rows, he can force the maximum shortest path to zigzag between the top and bottom rows on its way from the left column to the right one, resulting in a distance of ~(K+1)(N-1)+(M-1)~.

If even more roads need to be destroyed, the maximum shortest distance can no longer be increased. It's clear that the maximum possible shortest distance can never be larger than ~M(N-1)+2(M-1)-K~, as that's the total number of non-destroyed roads remaining. In fact, exactly this distance can always be achieved once at least ~M-1~ roads are destroyed – if more roads must be destroyed, they can be repeatedly destroyed from one "end" of the maximum shortest path, with each one decreasing its distance by just ~1~.

The above observations can be put together to form the following closed-form answer:

$$\displaystyle \min \begin{cases}(K+1)(N-1)+(M-1) \\ M(N-1)+2(M-1)-K\end{cases}$$