The problem is NP-complete. Here is a reduction from 3SAT-5, an NP-complete version of 3SAT in which every variable appears exactly 5 times (and so the number of variables and number of clauses are linearly related).
We start by constructing two set systems. The first system $\mathcal{S}$ consists of 6 sets $A_0,A_1,B_0,B_1,C_0,C_1$ and 15 elements $D = \{0,1\}^4 \setminus (1,1,1,1)$, and has the following property:
$$ |A_i \cup B_j \cup C_k| = \begin{cases} 14 & \text{if } i=j=k=0, \\ 13 & \text{otherwise}. \end{cases} $$
The set system is given by
$$\begin{align*}
A_i &= \{(a,b,c,d) \in D : a = i\}, \\
B_i &= \{(a,b,c,d) \in D : b = i\}, \\
C_i &= \{(a,b,c,d) \in D : c = i\}.
\end{align*}$$
The only elements not covered by $A_i \cup B_j \cup C_k$ are those of the form $(1-i,1-j,1-k,d)$. If $i = j = k = 0$ then there is one such element, otherwise there are two.
The second system $\mathcal{T}$ consists of $2n$ sets $X_1,Y_1,\ldots,X_n,Y_n$ and $O(n^2)$ elements, and has the following property. Call a family of $n$ sets out of $\mathcal{T}$ proper if it contains exactly one of each $X_i,Y_i$. All proper families of $n$ sets cover the same number of elements $M$, and each improper family of $n$ sets covers at least $M+1$ elements.
The set of elements consists of all unordered pairs of sets $\{S,T\}$ other than those of the form $\{X_i,Y_i\}$. Each set $S \in \mathcal{T}$ consists of all $2n-2$ pairs containing it. Let $\mathcal{F}$ be a family of $n$ sets, with complement $\overline{\mathcal{F}}$. The only elements not covered by $\mathcal{F}$ are those of the form $\{S,T\}$ where $S,T \in \overline{\mathcal{F}}$. If $\mathcal{F}$ is proper then so is $\overline{\mathcal{F}}$, and so there are $\binom{n}{2}$ elements not covered. If $\mathcal{F}$ is improper then so is $\overline{\mathcal{F}}$, and so there are fewer than $\binom{n}{2}$ elements not covered.
The reduction. Let $\phi$ be an instance of 3SAT-5 with $n$ variables and $m=5n/3$ clauses. For each clause $\phi_j$ there is a copy $\mathcal{S}_j$ of system $\mathcal{S}$. There is also a copy $\tilde{\mathcal{T}}$ of $\mathcal{T}$ in which each element is replaced by $N = 13m+1$ elements. The total number of elements is polynomial in $n$.
For each variable $x_i$ there are two sets $X_i^0$ and $X_i^1$. The set $X_i^0$ is the union of the following six sets:
- the set $X_i$ of $\tilde{\mathcal{T}}$
- for each clause $\phi_j$ containing $x_i$ at the first position, if $x_i$ appears positively, then the set $A_0$ of $\mathcal{S}_j$, otherwise the set $A_1$ of $\mathcal{S}_j$
- for each clause $\phi_j$ containing $x_i$ at the second position, either $B_0$ or $B_1$ (as above)
- for each clause $\phi_j$ containing $x_i$ at the third position, either $C_0$ or $C_1$ (as above)
The set $X_i^1$ is defined similarly as the union of the following six sets:
- the set $Y_i$ of $\tilde{\mathcal{T}}$
- for each clause $\phi_j$ containing $x_i$ at the first position, if $x_i$ appears negatively, then the set $A_0$ of $\mathcal{S}_j$, otherwise the set $A_1$ of $\mathcal{S}_j$
- for each clause $\phi_j$ containing $x_i$ at the second position, either $B_0$ or $B_1$ (as above)
- for each clause $\phi_j$ containing $x_i$ at the third position, either $C_0$ or $C_1$ (as above)
The problem is to decide whether there are $n$ sets which together cover $13m+NM$ elements (or less).
If $\phi$ is satisfiable, say with truth assignment $x_i$, then $\{X_i^{x_i} : 1 \leq i \leq n\}$ covers exactly $13m+NM$ elements. Conversely, suppose there is a way to cover at most $13m+NM$ elements. If the solution is improper then it covers at least $N(M+1) > 13m+NM$ elements (considering only $\tilde{\mathcal{T}}$). If it is proper then it corresponds to some truth assignment $x_i$, and it is easy to check that the number of elements covered is $13m+NM+Z$, where $Z$ is the number of falsified clauses. Hence $Z = 0$ and we conclude that $x_i$ is a satisfying assignment.