P5585 “SWTR-1” Doing Homework

Little $\mathrm{A}$ has a lot of homework to do every day.

Every day, Little $\mathrm{A}$ must do at least $w$ tons of homework. If he fails to reach the goal, he will be punished by Little $\mathrm{S}$ and die on the spot. Little $\mathrm{A}$ has $x$ energy points. Each time he does homework, Little $\mathrm{A}$’s energy decreases, and this is **irreversible**. Little $\mathrm{A}$’s energy cannot drop below $0$. Now, there are $n$ types of homework for Little $\mathrm{A}$ to choose from. Each type of homework has the following attributes: $x_i$: energy cost, i.e., doing one copy of this type of homework requires $x_i$ energy. $w_i$: weight, i.e., one copy of this type of homework weighs $w_i$ tons. $t_i$: deadline, i.e., after $t_i$ days from today, this homework can no longer be done. **There are infinitely many copies of each type of homework.** Since he has too much homework to ever finish, please arrange a homework plan for him to **maximize** the number of days he can survive. When the number of surviving days is maximized, maximize his remaining energy.

The first line contains two positive integers $x, w$, representing Little $\mathrm{A}$’s energy and the daily goal. The next line contains one positive integer $n$, indicating the number of types of homework. The next $n$ lines each contain three integers $x_i, w_i, t_i$.

Output two numbers separated by a space, representing the maximum number of days Little $\mathrm{A}$ can survive, and his remaining energy.

--- ### Sample Explanation On day $1$, Little $\mathrm{A}$ chooses to do $2$ copies of the second type of homework. The weight is $2 * 2 = 4$, and the remaining energy is $30 - 2 * 3 = 24$. On day $2$, Little $\mathrm{A}$ chooses to do $2$ copies of the second type of homework. The weight is $2 * 2 = 4$, and the remaining energy is $24 - 2 * 3 = 18$. At this point, he can no longer do the second type of homework $(t_2 = 2)$. On day $3$, Little $\mathrm{A}$ chooses to do $1$ copy of the third type of homework. The weight is $4$, and the remaining energy is $18 - 8 = 10$. On day $4$, Little $\mathrm{A}$ chooses to do $1$ copy of the third type of homework. The weight is $4$, and the remaining energy is $10 - 8 = 2$. At this point, he can no longer do the third type of homework $(t_3 = 4)$. Little $\mathrm{A}$ has no energy left to do any other homework, so he can survive at most $4$ days, with $2$ energy remaining. It can be proven that no better plan than this one can be found. --- ### Constraints  --- For $25\%$ of the testdata with $n \leq 5000$, the time limit is $1\ \mathrm{s}$ and the memory limit is $256\ \mathrm{MB}$. For the remaining test points, the time limit is $400\ \mathrm{ms}$ and the memory limit is $8\ \mathrm{MB}$. Translated by ChatGPT 5