International Mathematical Olympiad 1971 Problem 6

Let $A = (a_{ij})$ $(i, j = 1, 2, \ldots, n)$ be a square matrix whose elements are non-negative integers. Suppose that whenever an element $a_{ij} = 0$, the sum of the elements in the $i$th row and the $j$th column is $\geq n$. Prove that the sum of all the elements of the matrix is $\geq n^2/2$.