Finding a subset of nonnegative vectors with a coordinatewise large sum

Given a rational $a=p\mathrm{/}q$ and $N$ nonnegative $d$-dimensional real vectors $u_1$, …, $u_N$, we show that it is always possible to choose $(d-1)+\lceil (pN-d+1)/q\rceil$ofthemsuchthattheirsumis(componentwise)atleast$(p/q)(u_1+…+u_N)$\mathrm{.}Forfixed$d$and$a$,thisboundissharpif$N$ is large enough. The method of the proof uses Carath'eodory’s theorem from linear programming.