P5585 「SWTR-1」Doing Homework

小 $\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}$ 最多能活多少天，以及剩余的精力。

--- ### 样例说明 第一天，小 $\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$。 可以证明，找不到比该方案更优的方案了。 --- ### 数据范围  --- 对于 $n \leq 5000$ 中 $25\%$ 的数据，有时间限制 $1s$，空间限制 $256MB$。 其余测试点时间限制 $400ms$，空间限制 $8MB$。