For $k, l$ with $0 \le k \le r$ and $k+1 \le l \le s$, we introduce the auxiliary value
$$T(k, l) := m_l + \sum_{i=1}^{k} m_i.$$

We claim that these $\frac{1}{2}(r+1)(2s - r)$ auxiliary values are all pairwise distinct: Let us assume that $T(k, \ell) = T(u, v)$. Without loss of generality $k \le u$, so that this equality turns into
$$m_{\ell} = m_{v} + \sum_{i=k+1}^{u} m_{i}.$$
But then $m_{\ell}$ can be written as a sum of distinct other numbers in the sequence, unless $\ell = v$ and $k = u$ holds. Hence the auxiliary values indeed are distinct. As altogether there are $\frac{1}{2}(r+1)(2s - r)$ auxiliary values, the largest value $T(r, s)$ must be at least $\frac{1}{2}(r+1)(2s - r)$. This yields
$$\frac{1}{2}(r+1)(2s - r) \le T(r, s) = m_s + \sum_{i=1}^{r} m_i \le m_s + \sum_{i=1}^{r} (m_r - r + i).$$
Here we used $m_i \le m_r - r + i$, which follows as the sequence is increasing. The above inequality can be rewritten into
$$rs + s - r \le r \cdot m_r + m_s,$$
which immediately implies the desired inequality from the problem statement.