PL-OM 1984 Problem 2

Let $n$ be a positive integer. For all $i, j \in \{1,2,...,n\}$ define $a_{j,i} = 1$ if $j = i$ and $a_{j,i} = 0$ otherwise. Also, for $i = n+1,...,2n$ and $j = 1,...,n$ define $a_{j,i} = -\frac{1}{n}$ . Prove that for any permutation $p$ of the set $\{1,2,...,2n\}$ the following inequality holds: $\sum_{j=1}^{n}\left|\sum_{k=1}^{n} a_{j,p}(k)\right| \ge \frac{n}{2}$