Background

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

Problem Description

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.

Input Format

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 Format

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

30 4
3
5 3 8
3 2 2
8 4 4

4 2

100 3
2
3 2 8
2 1 5

8 57

Hint

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