$$$O(n)$$$.

This is a warmup. Map each pair $$$(x, y)$$$ to $$$x + y$$$, and find the $$$n$$$ smallest resulting values. Their original pairs are the $$$n$$$ pairs you should choose.

Can be done in linear time by finding the median in linear time.

Why can we change all our pairs of integers to a single integer? For which other functions $$$f$$$ could this work?

$$$O(n^2M^2)$$$

Solve with dynamic programming, with the following states:

For each $$$(i, j, x, y)$$$, the value would be $$$1$$$ if we can use exactly $$$j$$$ pairs from the first $$$i$$$ pairs, such that their pointwise sum is $$$(x, y)$$$, and $$$0$$$ otherwise. Here we have $$$1 \leq i \leq 2n, 0 \leq j \leq n, 0 \leq x, y \leq M$$$, so overall $$$O(n^2M^2)$$$ states.

Iterate over all pairs from first to last. On the $$$i$$$-th pair $$$(p,q)$$$, iterate over all $$$(j, x, y)$$$ and set $$$dp[i][j][x][y] = 1$$$ only if one of the following values is 1: $$$dp[i-1][j][x][y], dp[i-1][j-1][x-p][y-q]$$$. For each pair it takes $$$O(nM^2)$$$ time, so overall $$$O(n^2M^2)$$$ time here.

In the end, iterate over all $$$(x, y)$$$, and across all of them that satisfy $$$dp[2n][n][x][y] = 1$$$, take the minimum $$$f(x,y)$$$.

With another table of the same size you can reconstruct the chosen pairs. Overall $$$O(n^2M^2)$$$ time and space.

• You most likely cannot solve this problem in complexity $$$O(\poly n)$$$