Mouse Meets Cheese

Arya has a pet mouse named Jack. She put Jack in a grid with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$). There are $K$ cheese wedges scattered over the grid; for each wedge, we know how long it takes Jack to eat it. Let's denote the cell in row $r$ and column $c$ by $(r, c)$. Initially, Jack is in the cell $(1, 1)$. When Jack is in a cell $(r, c)$, he can move