P2676 [USACO07DEC] Bookshelf B

Farmer John recently added a huge bookshelf to the cows' library. Even though it is very large, it was almost instantly filled with all kinds of books. Now, only a little space remains at the very top of the shelf. All $N(1 \le N \le 20,000)$ cows each have a fixed height $H_i(1 \le H_i \le 10,000)$. Let the sum of all cows' heights be $S$. The bookshelf has height $B$, and it is guaranteed that $1 \le B \le S < 2,000,000,007$. To reach the top of the bookshelf, which is higher than the tallest cow, the cows have to perform an acrobatic act by standing on each other's backs, forming a "cow tower." The height of the tower is the sum of the heights of all cows in it. To place items on the top of the bookshelf, the total height of the cows must be at least the height of the bookshelf. Obviously, the more cows in the tower, the less stable it becomes. Therefore, the cows want to use as few cows as possible while still being able to reach the top of the bookshelf. They ask you to compute this minimum number.

- Line $1$: Two integers separated by a space: $N$ and $B$. - Lines $2\dots N+1$: Line $i+1$ contains $1$ integer: $H_i$.

- Line $1$: Output $1$ integer — the minimum number of cows needed to stack into a tower to reach the top of the bookshelf.

Input description: There are $6$ cows, the bookshelf height is $40$, and the cows’ heights are between $6\dots19$. Output description: One way to reach height $40$ using only $3$ cows: $18+11+13$. Of course, there are other ways, which are not listed here. Translated by ChatGPT 5