对于某 $k$ 个位置，如果有他们可能的最小和 $l$，可能的最大和 $r$，那么对于 $\forall i\in[l,r]$，$i$ 都可能是这 $k$ 个位置的和。这个是可以一步一步调整依次得到的。并且在这个调整的过程中，我们可以尽量使得这 $k$ 个位置的值接近。进一步可以发现，如果要让这 $k$ 个位置的值均为 $w$，那么一定有 $w\in[l,r]$。

于是用二阶差分预处理 $l,r$，然后对于每个 $k$ 都做一遍二分即可。时间复杂度 $O(n+m\log n)$。