小 \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。
可以证明，找不到比该方案更优的方案了。
1 \leq n \leq 5000, 1 \leq x \leq 2×10^{9} ,1 \leq x_i \leq 2×10^9 ,1 \leq w \leq 5000,1 \leq w_i \leq 5000,1 \leq t \leq 10^8
用户上传