The Right Triangle Game

I am looking for a deeper understanding, particularly the optimum strategy and the maximum score as a function of grid size, of the following (single-player) game played with an $n$ by $m$ grid:

($6 \times 6$ example)

Rules

1. Start with a grid made of $n$ by $m$ squares and execute as many moves as you can
2. A move consists of making a single straight cut that cuts off a right triangle with the condition that the cut must start and end on a grid point
3. Your score is the number of moves you made

Example 1: "Naive" strategy

The naive strategy consists of always picking the move that cuts off the smallest possible right triangle.

For grids larger than $2 \times 2$, the naive strategy is game over after four moves:

Example 2: A better try

The following game run, although it starts by cutting off half the grid, contains twenty moves:

Notes

• Although the examples all use a $6 \times 6$ square grid, I am particularly interested also in non-square rectangular boards (where the grid units are still squares, of course).
• The triangles cut off in the example games are all isosceles. Note that this is not required by the rules!
• Since the smallest triangle that can ever be legally cut off is half of a grid unit, $2nm$ is a trivial upper bound for the maximum score.
• Unrelated to the original question, this single-player game can also be converted to an interesting two-player game: Players alternate making moves; the last player to make a legal move wins.

The maximum score function

Let $f(n,m)$ denote the maximum score (number of moves) attainable with an $n \times m$ grid.

The following is known about $f$:

$f(n,m) = f(m,n)$ (symmetry)

$f(n,m) \leq 2nm-1$ (see hardmath's comment)

$f(n,1) = 2n-1$ (see hardmath's comment)

$f(n,2) = 3n$ (can be obtained with some thinking)

$f(1,1) = 1$ (corollary of above formula)

$f(2,2) = 6$ (corollary of above formula)

$f(3,3) = 11$ (obtained by manual trial and error)

$f(4,4) = 16$ (obtained by manual trial and error, corrected by hardmath's comment)

$f(n,m) \ge 2\min(n,m) + 3\max(n,m) - 4$ (see hardmath's comment), in particular

$f(n,n) \ge 5n - 4$

Note that the last bound is actually strict for $1 \le n \le 4$, so this bound (and the associated strategy) might already be the answer to the entire question.

Given that the board m x n may not necessarily square, perhaps for the non-square boards, you must use a method that treats it as a non square board. Im implying that some of the triangles that are cut off are likely to not be isosceles due to the different dimensions and in fact the most optimal way may be cutting off triangles in the ratio of the rectangle of sorts.

Another possibility is sectioning the rectangular board into a square and non-square board. Then you use the optimal method for solving the square and then continue to cut off right triangles on the left over non-square section

I hope this provides some insight to this problem