题目背景

小 $\mathrm{A}$ 每天都有很多作业要写。

题目描述

每天，小 $\mathrm{A}$ 都要写至少 $w$ 吨的作业，如果他达不到目标，就会受到小 $\mathrm{S}$ 制裁并且当场去世。

小 $\mathrm{A}$ 有 $x$ 点精力，每次写作业都会降低小 $\mathrm{A}$ 的精力，且不可逆，小 $\mathrm{A}$ 的精力不可以降为负数。

现在，有 $n$ 种作业给小 $\mathrm{A}$ 选。

每种作业有如下的属性：

• $x_i$：消耗的精力，即写一份这种作业需要 $x_i$ 的精力。

• $w_i$：重量，即这种作业一份有 $w_i$ 吨。

• $t_i$：截止日期，即从今天过了 $t_i$ 天之后，这个作业不可以再写。

每种作业都有无限个。

因为他的作业实在是多得写不完，所以请你为他安排一种写作业的方案，最大化他能存活的天数，当存活天数已最大化时，最大化他剩余的精力。

输入格式

第一行两个正整数 $x,w$ ，即小 $\mathrm{A}$ 的精力和每天的目标。

接下来一行一个正整数 $n$ ，表示作业的种数。

接下来 $n$ 行，每行三个整数 $x_i,w_i,t_i$。

输出格式

输出两个由空格隔开的数，分别表示小 $\mathrm{A}$ 最多能活多少天，以及剩余的精力。

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

提示

样例说明

第一天，小 $\mathrm{A}$ 选择写 $2$ 份第二种作业，重量为 $2 * 2=4$，剩余精力为 $30-2 * 3=24$。

第二天，小 $\mathrm{A}$ 选择写 $2$ 份第二种作业，重量为 $2 * 2=4$，剩余精力为 $24-2 * 3=18$。

至此，不可以再写第二种作业 $(t_2=2)$。

第三天，小 $\mathrm{A}$ 选择写 $1$ 份第三种作业，重量为 $4$，剩余精力为 $18-8=10$。

第四天，小 $\mathrm{A}$ 选择写 $1$ 份第三种作业，重量为 $4$，剩余精力为 $10-8=2$。

至此，不可以再写第三种作业 $(t_3=4)$。

小 $\mathrm{A}$ 没有精力再去写别的作业了，所以他最多能活 $4$ 天，剩余精力为 $2$。

可以证明，找不到比该方案更优的方案了。

---

数据范围

::cute-table{tuack}

$n$	$x$	$x_i$	$w$	$w_i$	$t_i$	$\text{score}$
$\le2$	$\le30$	<	$\le5$	<	$\le10$	$5\%$
$\le5$	$\le500$		$\le10$		$\le50$	$15\%$
$\le10$	$\le1000$		$\le25$		$\le200$	$25\%$
$\le50$	$\le10^5$		$\le50$		$\le10^4$	$40\%$
$\le100$	$\le10^9$		$\le100$		$\le3\times10^7$	$50\%$
$\le5000$	$\le2\times10^9$		$\le5000$		$\le10^8$	$100\%$

---

对于 $n \leq 5000$ 中 $25\%$ 的数据，有时间限制 $1s$，空间限制 $256MB$。

其余测试点时间限制 $400ms$，空间限制 $8MB$。