Problem Background

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

Problem Description

Every day, Little $\mathrm{A}$ needs to complete at least $w$ tons of homework. If he fails to meet this goal, he will be sanctioned by Little $\mathrm{S}$ and will die on the spot.

Little $\mathrm{A}$ has $x$ points of energy. Each time he does homework, his energy decreases, and this decrease is irreversible. Little $\mathrm{A}$'s energy cannot drop below zero.

Now, there are $n$ types of homework for Little $\mathrm{A}$ to choose from.

Each type of homework has the following attributes:

$x_i$: The energy consumed, i.e., doing one unit of this homework requires $x_i$ energy.

$w_i$: The weight, i.e., one unit of this homework weighs $w_i$ tons.

$t_i$: The deadline, i.e., after $t_i$ days from today, this homework cannot be done anymore.

There are unlimited quantities of each type of homework.

Since his homework is truly endless, please help him arrange a plan to maximize the number of days he can survive. When the number of survival days is maximized, also maximize his remaining energy.

Input Format

The first line contains two positive integers $x$ and $w$, representing Little $\mathrm{A}$'s energy and the daily goal, respectively.

The next line contains a positive integer $n$, representing the number of types of homework.

The following $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.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4 2

Sample Input #2

100 3
2
3 2 8
2 1 5

Sample Output #2

8 57

Notes

Sample Explanation

On the first day, Little $\mathrm{A}$ chooses to do 2 units of the second type of homework, weighing $2 * 2 = 4$ tons, with remaining energy $30 - 2 * 3 = 24$.

On the second day, Little $\mathrm{A}$ chooses to do 2 units of the second type of homework, weighing $2 * 2 = 4$ tons, with remaining energy $24 - 2 * 3 = 18$.

At this point, he cannot do the second type of homework anymore $(t_2 = 2)$.

On the third day, Little $\mathrm{A}$ chooses to do 1 unit of the third type of homework, weighing $4$ tons, with remaining energy $18 - 8 = 10$.

On the fourth day, Little $\mathrm{A}$ chooses to do 1 unit of the third type of homework, weighing $4$ tons, with remaining energy $10 - 8 = 2$.

At this point, he cannot do the third type of homework anymore $(t_3 = 4)$.

Little $\mathrm{A}$ does not have enough energy to do any other homework, so he can survive a maximum of 4 days with 2 units of energy remaining.

It can be proven that no better plan exists.

Data Range

For $25\%$ of the data where $n \leq 5000$, there is a time limit of $1$ second and a space limit of $256$ MB.

For the remaining test points, there is a time limit of $400$ ms and a space limit of $8$ MB.

见题面 Input 部分

见题面 Output 部分