Let's assume the grid is arbitrarily large for now. The optimal solution when ~K = 0~ involves just ~2~ trees, one to the right of the top-left cell, and the other below it. When ~K = 1~, we can add just ~2~ more trees to block off the bottom-right cell in the same fashion. For ~K = 2~, we'll need to add a diagonal line of ~3~ additional trees to increase the "width" of one of those barricades from ~1~ to ~2~, and so on. As can be seen, the differences between the subsequent answers for all possible values of ~K~ (assuming an initial answer of ~0~) are ~2, 2, 3, 3, 4, 4~, etc.

So far, this is all independent of the size of the grid. So exactly what effect do the grid's dimensions have? Firstly, the shortest path from the top-left to the bottom-right cell passes through ~N+M-3~ other cells, meaning that if ~K \ge N+M-3~, the answer is -1, even if every cell on such a path contained a tree, they could all be cut down. Otherwise, if we assume that the grid is wider than it is tall (~N \le M~), then the lengths of our diagonal barricades added at each step will eventually cap out at ~N~, yielding a sequence of answer differences ~2, 2, 3, 3, \dots, N, N, N~.

What remains is computing the sum of the first ~K+1~ terms of this sequence to yield the total answer. This can be done trivially in ~\mathcal O(N+M)~ time, but that's too slow to get full marks, so a closed-form expression will be required. We should split the sequence into two portions – the first ~2(N-1)~ terms of the sequence, which are increasing in pairs, and the remaining terms, each of which is ~N~. Computing the sum of the required terms in the second portion is then trivial. The first portion can once more be split into two separate arithmetic sequences ~2, 3, \dots, N~. We can then determine how much of each of those sequences we need (by dividing ~K+1~ by ~2~, rounded up and down), and compute their sums in standard fashion in ~\mathcal O(1)~ time.