P17379 [PacNW 2025] Bouquet of Balloons

On their journey to the World Finals, Team Shuchiin Academy must first conquer the North America Championship. The problem set contains $n$ problems, and problem $i$ takes $s_i$ minutes to solve. The team may solve the problems in any order, but it cannot work on multiple problems in parallel. It must finish its current problem before starting another one. Whenever the team solves a problem, the judges immediately bring it a fully inflated balloon. Chika Fujiwara, the team's resident troll, decides to tie all the balloons to the team's lucky die so that it floats. When the team receives a balloon, it contains $1$ liter of helium and can lift $1$ gram. Every balloon has a lifetime of $d$ minutes. It deflates at a constant rate of $1/d$ liters per minute, and its lifting capacity decreases at the same rate. For example, after $d/3$ minutes, a balloon can lift $2/3$ grams. After $d$ minutes, its lifting capacity is $0$. The die floats if, at any moment, the total lifting capacity of all the team's balloons is at least the die's mass $m$. The mass of the balloons themselves is negligible. Given the problem-solving times, the balloon lifetime $d$, and the die mass $m$, find the minimum number of problems Team Shuchiin Academy must solve to make the die float. If it is impossible, output $-1$.

The first line contains three integers $n$, $d$, and $m$ ($1\le n,d,m\le10^5$): the number of problems, the lifetime of each balloon, and the mass of the die. The second line contains $n$ integers $s_1,s_2,\ldots,s_n$ ($1\le s_i\le10^5$), the times needed to solve the problems.

Output the minimum number of problems the team must solve to make the die float, or $-1$ if this is impossible.