Во первых, если вычесть уже расставленные числа из ограничений на сумму чисел в соответствующих строках и столбцах, то задача сведется к аналогичной. Ответ будет различаться ровно на эти числа. Значит, далее будем считать, что все изначально расставленные числа равны 0.

Построим сеть из N+M+2 вершин. Вершинами будут строки матрицы, ее столбцы и две дополнительные вершины: исток и сток. Из истока будут вести дуги в вершины, соотвествующие строкам с пропускной способностью R_i. Из вершин, соответствующих столбцам, будут идти дуги в сток с пропускной способностью C_j. Вершины, соответствующие i-й строке и j-му столбцу будут соединены дугой тогда и только тогда, когда на пересечении i-й строки и j-го столбца в оригинальной матрице стояло число -1. Пропускная способность таких дуг будет равна бесконечности. Максимальный поток в этой сети и будет ответом на поставленную задачу.

Сеть можно не строить явно, а продолжать работать с матрицей.