International Mathematical Olympiad 1994 Problem 1

Let $m$ and $n$ be positive integers. Let $a_1, a_2, \ldots, a_m$ be distinct elements of $\{1, 2, \ldots, n\}$ such that whenever $a_i + a_j \leq n$ for some $i, j$, $1 \leq i \leq j \leq m$, there exists $k$, $1 \leq k \leq m$, with $a_i + a_j = a_k$. Prove that

$$\frac{a_1 + a_2 + \cdots + a_m}{m} \geq \frac{n + 1}{2}.$$