結論は以下のとおりです。

\[\displaystyle S_i := \sum_{j=i}^{M-1} A_j 2^{j-i}\]

（自然言語でいえば、重さ \(2^i\) 以上の荷物を \(2^i\) を \(1\) 単位としたときの総量）とすれば、答えは以下の式で表される \(C\) となります。

\[\displaystyle C = \max_{0 \le i \lt M} 2^i \left\lceil\frac{S_i}{N}\right\rceil\]

これが下界であることは \(\displaystyle S_i \le N\left\lfloor\frac{C}{2^i}\right\rfloor\) がすべての \(i\) で成り立つことが必要であることから、簡単に示されます。

これが可能なことについては、具体的にこれを満たすような packing が得られればよいです。そして、これは maspy さんの解説に書かれているような貪欲で可能です。（TODO）