题目内容

现在塔子哥有火药枪若干， 以及数量有限的火药，每种火药枪的威力不尽相同，且在每次开火之前都需要一定时间填充火药， 请你帮助塔子哥在给定的时间结束之前或者火药存量耗尽之前给予敌人最大的伤害。

限制:

1. 火药枪每次开火的威力一样；
2. 火药剩余量不小于火药枪的消耗量，该火药枪才能开火；
3. 填充火药之外的时间忽略不计；
4. 不同种火药枪可以同时开火。

输入描述

第一行，整数 $N$ ， $M$ ， $T$ ， $N$ 表示火药枪种类个数， $M$ 表示火药数量， $T$ 表示攻城时间，$1 \leq N,M,T \leq 1000$。

接下来 $N$ 行，每一行三个整数 $A$ ， $B$ ， $C$ 。分别表示火药枪的威力，火药枪每次攻击消耗的火药量，火药枪每次攻击填充火药的时间，$0\leq A,B,C \leq 100000$。

输出描述

输出在给定的时间结束之前或者火药存量耗尽之前给予敌人最大的伤害。

样例

样例一：

输入

3 88 30
10 7 5
5 3 1
4 4 8

输出

145

样例解释

总共有 $3$ 种火药枪，火药存量 $88$ ， 攻城时间 $30$ ;

第 $1$ 种火药枪威力 $10$ ，每次攻击消耗火药 $7$ ，每次攻击填充火药时间 $5$ ；

第 $2$ 种火药枪威力 $5$ ，每次攻击消耗火药 $3$ ，每次攻击填充火药时间 $1$ ；

第 $3$ 种火药枪威力 $4$ ，每次攻击消耗火药 $4$ ，每次攻击填充火药时间 $8$ ；

样例二：

输入

2 10 15
2 2 2
3 3 3

输出

10

样例解释

总共有 $2$ 种火药枪，火药存量 $10$ ，攻城时间 $15$ ；

第 $1$ 种火药枪威力 $2$ ，每次攻击消耗火药 $2$ ，每次攻击填充火药时间 $2$ ；

第 $2$ 种火药枪威力 $3$ ，每次攻击消耗火药 $3$ ，每次攻击填充火药时间 $3$ ；