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.