I've spent some time on the following problem, which is quite generic:

You are given $$$n$$$ pairs of integers $$$(x_i, y_i)$$$, where $$$n$$$ is even, and $$$1 \leq x_i, y_i \leq M$$$. Your goal is to choose exactly $$$\frac{n}{2}$$$ of them, such that their pointwise sum $$$(X, Y)$$$ minimizes the cost function $$$f(X, Y)$$$. What is the best time complexity you can achieve, given some properties about the function $$$f$$$?