Let's try to solve the following subproblem: Given two sequences $A$ and $B$, what is the optimal pairing for these two sequences? Let $A_{max}$ be the largest number in sequence $A$ (if more than one exists, choose any one), and $B_{min}$ be the smallest number in sequence $B$. Choose some pairing which contains the pair $(A_{max},B_{min})$. Is this optimal? There are two cases we need to address:

• $(A_{max}+B_{min})$ is the largest sum in the chosen pairing. If this is the case, it is quite obvious that no other number from $B$ can reduce this sum. The best you can do is select another instance of $B_{min}$, if more than one is present, and achieve the exact same sum. So, if $(A_{max}+B_{min})$ is the largest sum in the chosen pairing, there is no way to improve that.

• $(A_{max}+B_{min})$ is not the largest sum in the chosen pairing. Let $(A_x,B_x)$ denote the pair with the largest sum. Can we improve this by breaking the $(A_{max},B_{min})$ pair? We could try creating pairs $(A_{max},B_x)$ and $(A_x,B_{min})$. It is clear that now the sum $A_x+B_{min}$ is equal or smaller than $A_x+B_x$. However, $A_{max}+B_x$ is now larger or equal than $A_x+B_x$ because $A_{max}$ is larger than or equal to $A_x$. This has now created a new largest sum, larger than or equal to the previous one.

So we conclude that it is not possible to improve the solution by not using $(A_{max},B_{min})$. This gives us a good starting point for a greedy approach.