UVa 434 - Matty's Blocks

Problem Statement:
UVa 434 - Matty's Blocks

Summary:
This problem pertains to a matrix of size K x K, where each entry is a non-negative integer.
Let the maximum values on each row be max_row[0 .. K-1], and the maximum values on each column be max_col[0 .. K - 1].

E.g.          
[ 1 4 2 5 3 ]  --> 5
[ 8 1 7 6 0 ]  --> 8
[ 3 3 4 1 5 ]  --> 5  max_row
[ 6 5 0 3 2 ]  --> 6
[ 2 4 1 6 6 ]  --> 6
  v v v v v
  8 5 7 6 5
  max_col

Our job is to fill in the matrix to fulfil those requirements. In general there are more than one way to do it. Compute:
1. Minimum sum of entries possible.
2. Maximum sum of entries possible.

Note that no constraint is placed on K in the original problem statement. It can be small, it can be very large.