Maximum of sum is at most the sum of maxima

Here's a methodical way to solve the problem.

First, you're trying to show $$ \max_x \text{something} \le \text{something else} $$ This is equivalent to $$ \text{for all $x$,}\quad \text{something}\le\text{something else} $$ So let $x$ be arbitrary and let's show $$ \sum_y f(x,y) \le \sum_y \max_x f(x,y) $$ To avoid confusion, let me change the $x$ on the right, because it's not the same as the $x$ we just chose. $$ \sum_y f(x,y) \le \sum_y \max_z f(z,y) $$ Anyway, to show $\sum_y \text{something} \le \sum_y \text{something else}$, the simplest thing that could possibly work is to show $\text{something}\le\text{something else}$ and then sum over $y$. So let's try that: we want to show $$ f(x,y) \le \max_z f(z,y) $$ And now... well, yes, this is true: the LHS is one of the values considered in the maximum on the RHS, so of course the RHS is larger.

Let $x\prime$ be the $x$ which maximizes the LHS. Then, for every term on the RHS you have: $f(x\prime, y) \leq \max_x f(x,y)$