题目背景

那天，是家鸡帝国最黑暗的时刻......

---

115年，刚建国的宓果野心磅礴，决心冲击西南，也就是家鸡帝国。
那天，守将正悠闲地在城墙上喝茶。可一支暗箭忽然飞来，打破了这份宁静。
在少数民族和刁悍民风的支持下，宓果大军势如破竹，攻到了家鸡首都鸡脚城下。
鸡脚城的守将战死，城中兵力也早已空虚。虽然来犯之敌已被击退，但一个确切的情报告诉我们：他们在 \(t\) 秒后就会来临。
家鸡面色凝重地望向远方。
留给他的时间不多了， 他马上要成为宓果吃的炸鸡了 。

题目描述

家鸡清点了城中所有的金钱，共有 \(m\) 元。(不考虑增长的情况)
他又找到了你，并把所有的消息和决定权都给了你。这也说明你，我的朋友，你是家鸡帝国最后的希望。
现在，城中有 \(n\) 个兵种。第i种兵能增加\(s_i\)防御力。每个兵种都可以由两种方式获得：招募 or 直接购买。
* 招募： 第i种兵将会消耗 \(a_i\) 金钱和 \(b_i\) 秒时间。
* 直接购买： 第i种兵将会消耗 \(a_i * 5 * b_i\) 金钱，但不消耗时间。
求家鸡最多在宓果大军到来之前积攒多少防御力。

输入样例

第一行，三个整数，分别为 \(n\),\(m\),\(t\)。
接下来2~n+1行，三个整数，分别为\(a_i\),\(b_i\),\(s_i\)。

sample1

2 10 10
1 1 5
10 10 10

sample2

2 100 0
1 114 5
2 514 11

输出样例

共一行，一个整数，指最多能积攒多少防御力。

sample1

50

sample2

0

提示

\(n <= 100|m,t <= 1000|a_i,b_i,s_i <= 1000\)