combinatorics – Can this special case of bin packing be solved in polynomial time?

Consider a set of $n$ integers, where each integer is between $1$ and $3 M$. The sum of all integers is $3 S$. There are three bins. The capacity of each bin is $C = S + M$.
Is there a polynomial-time algorithm to decide whether all integers can be packed into the bins?

To explain why this specific case is special, consider some variants of the problem:

  • When $C$ is not fixed, the problem is NP-hard, since it is a special case of the bin-packing problem.
  • When $C = S$, the problem is NP-hard, since it is equivalent to 3-way number partitioning.
  • When $C geq S + 2 M$, the problem is easy since the answer is always “yes”. Proof: put the agents in an arbitrary order into the bins as long as there is room. Suppose by contradiction that not all integers are packed; let $x$ be some remaining integer. Then the sum in each bin is larger than $C-x$, so the sum in all bins is more than $3 C – 3 x geq 3 S + 6 M – 3 x$.
    Since $x leq 3 M$, this sum is larger than $3 S + 2 x – 3 x = 3 S – x$. But then the sum of all integers plus $x$ is larger than $3 S$ – a contradiction.

The case $C = S+M$ is between these extremes: it is larger than $S$ for which the problem is hard, but smaller than $S+2M$ for which the answer is always yes.

Is this case is easy or hard?