Prove that $(x_{1}+x_{2}+\cdots+x_{n})(y_{1}+y_{2}+\cdots+y_{n})\le \max_{1\le i,j\le n}(x_{i}+y_{j})$(PFTB 19) Let$x_{1},x_{2},\cdots,x_{n}$ and $y_{1},y_{2},\cdots,y_{n}$, be positive real numbers such that for all positive $t$ there are at most $\dfrac{1}{t}$ pairs $(i, j)$ satisfying $x_{i}+y_{j}\ge t$. Prove that
$$(x_{1}+x_{2}+\cdots+x_{n})(y_{1}+y_{2}+\cdots+y_{n})\le \max_{1\le i,j\le n}(x_{i}+y_{j})$$
the problem is from Titu Andreescu (Problems from the book) chapter 19: there a such hard problem for me:
First I see this left hand side,I want  try use AM-GM inequaliy
$$(x_{1}+x_{2}+\cdots+x_{n})(y_{1}+y_{2}+\cdots+y_{n})\le\left(\dfrac{\sum_{i=1}^{n}(x_{i}+y_{i})}{2}\right)^2$$ But it doesn’t seem to require a condition.
 A: Let's start by reformulating the problem slightly.
We may reorder the $x_i$ and $y_j$ in decreasing order so that $x_1\ge\cdots x_n>0$ and $y_1\ge\cdots y_n>0$. This way, the right-hand side is just $x_1+y_1$.
Next, take the list of sums $x_i+y_j$ and sort them in decreasing order into $u_1\ge\cdots\ge u_{n^2}>0$. Using $t=1/(k-\epsilon)$ for some small $\epsilon>0$, the number of $u_r\ge t$ is at most $k-\epsilon$, which is less than $k$, so $u_k<1/(k-\epsilon)$. As $\epsilon\rightarrow0$, this translates into $u_k\le 1/k$.
Let $S_x=\sum_{i=1}^n x_i$, $S_y=\sum_{j=1}^n y_j$, and $S=S_x+S_y$. This makes
$$
\sum_{k=1}^{n^2} u_k = \sum_{1\le i,j\le n} x_i+y_j = nS.
$$
If we denote $A=u_1=x_1+y_1$, what we want to prove is that $S_xS_y\le A$. However, $S_xS_y\le(S/2)^2$, so we want to bound $S$. As $u_k\le A$ and $u_k\le 1/k$, we have
$$
nS = \sum_{k=1}^{n^2} u_k
\le \sum_{k=1}^{n^2} \min\left(A,\frac{1}{k}\right)
\le \int_0^{n^2} \min\left(A,\frac{1}{s}\right)\,ds
=\begin{cases}
1+\ln(An^2)&\text{if}&A\ge 1/n^2\\
An^2&\text{if}&A\le 1/n^2
\end{cases}
$$
which bounds $S$ in terms of $n$ and $A$.
We now wish to prove that $(S/2)^2\le A$. If we write $a=\sqrt{A}$, this translates to proving that $S/2a\le 1$, so we investigate the bounds of $S/2a$. Using $\ln u\le u-1$, we get
$$
\frac{S}{2a}\le
\begin{cases}
\frac{1+2\ln(an)}{2an}\le\frac{2an-1}{2an}\le1
&\text{if}&an\ge1\\
\frac{a^2n^2}{2an}\le\frac12&\text{if}&an\le1
\end{cases}
$$
which proves that $S/2\le a=\sqrt u_1$, and in turn that
$$
S_xS_y \le \left(\frac{S}{2}\right)^2 \le a^2 = u_1 = x_1+y_1.
$$
And this is what we were supposed to prove.
