, 2013

Solution:
Answer: $54$

The key is to realize none of the primes can be $2$, $3$, or $5$, or else we would have to use one of them twice. Hence $p$, $q$, $r$, $s$ must lie among $7$, $11$, $13$, $17$, $19$, $23$, $29$, $\ldots.$ These options give remainders of $1$ $(\bmod 2)$ (obviously), $1$, $-1$, $1$, $-1$, $1$, $-1$, $-1$, $\ldots$ modulo $3$, and $2$, $1$, $3$, $2$, $4$, $3$, $4$, $\ldots$ modulo $5$.

We automatically have $2 \mid p q - r s$, and we have $3 \mid p q - r s$ if and only if $p q r s \equiv (p q)^2 \equiv 1$ $(\bmod 3)$, i.e. there are an even number of $-1$ $(\bmod 3)$'s among $p$, $q$, $r$, $s$.

If $\{p, q, r, s\} = \{7, 11, 13, 17\}$, then we cannot have $5 \mid p q - r s$, or else $12 \equiv p q r s \equiv (p q)^2 (\bmod 5)$ is a quadratic residue. Our next smallest choice (in terms of $p + q + r + s$) is $\{7, 11, 17, 19\}$, which works: $7 \cdot 17 - 11 \cdot 19 \equiv 2^2 - 4 \equiv 0 (\bmod 5)$. This gives an answer of $7 + 17 + 11 + 19 = 54$.