弗林戒指
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述


驰名于世的义贼弗林的戒指。
装备重量数值越轻，攻击力越高。
弗林借助风的力量战斗，
是孱弱贫困人们的英雄。
而崇拜者也心知肚明：
一切不过是童话故事罢了。
该题目有一句话描述，可以直接看最后一段。

你是一个活尸化严重的不死人，带着你的全部家当——一枚弗林戒指，来到了艾尔登法环的世界。弗林戒指的作用是：当你的负重占比小于 的时候，每减少 的负重占比就增加 的伤害；例如，当你负重占比为 的时候，你的伤害会提升 。来到了艾尔登法环世界的你仍然是一个弱鸡，为了使自己变强，你偷师了“接肢”的秘术。在你持续不断的努力之后，终于收集到了 n-2 个义肢，让自己成了有 n 只手的怪物。你觉得自己已经变得非常强，可以去挑战（偷袭）强大的出血狗薪王。为了应战强大的薪王，你需要进行充分的准备。
由于你有 n 只手，因此你可以装备至多 n 件武器，每一件武器有三个属性：重量 w，单次攻击的伤害 ATK、攻击速度 AS。可以简单的认为，你手持一把武器，从 0 时刻开始发动攻击，你会在第 AS 时刻对敌人造成 ATK 的伤害。
你的 n 只手只可以同时发动攻击，等最慢的武器攻击结束以后你才能发动第二次攻击。也就是说你在 0 时刻发动了第一次攻击，那么在 时刻你可以发动第二次攻击。不过很可惜，你去挑战的是强大的出血狗薪王，虽然你是偷袭它，但是你只可以发动一次攻击，如果一次攻击过后你无法击杀它，那么它会扭过头一口咬死你。为了避免意外，你要争取在最短的时间内，仅用一次攻击就击杀它。
已知狗薪王的血量为 H，你的最大负重为 W（为了简便，最大负重永远为 100）。如果你的装备总重量超过了最大负重，那么你将无法行动。你的背包里有 m 件武器，你想要好好计算一下你可以一次击杀狗薪王的最小时间 t。别忘了你的弗林戒指，在你不佩戴弗林戒指且不装备任何武器的时候你的负重为 0，那么你在佩戴弗林戒指以后负重就会变为 2，同时获得弗林戒指的增益：当负重占比在 及以下的时候，每减少 的负重就增加 的攻击力，这个增幅作用在你所有武器的攻击力和上。例如，你增加了 的攻击力，那么你在 t 时刻造成的攻击力就是 。
换句话说，你有 m 件武器和 1 件饰品，你可以从中选择至多 n 件武器以及 1 件饰品装备在身上，每件武器包括三个属性：w,ATK,AS。分别表示武器的重量，伤害和攻击时长。饰品仅有重量  以及一项增益：假设你此时选择的装备质量（此时仅包含武器）和为 ，所选武器的伤害和为 ，你可以选择佩戴该饰品使得你的装备质量（包括武器和的饰品）变为，并使你所选的武器伤害和变为。请你找出最小的整数 t，满足这些要求：你所选的各个武器的 AS 属性都不能超过 t；你所选武器的伤害和必须不小于 H（注意佩戴饰品对伤害和负重的影响）；装备质量和（包括武器和饰品）不可以超过 100。其中 n,m,H 以及每件装备的属性均为输入值。

输入描述:

第 1 行包括三个正整数：n,m,H。分别代表你的手臂数（即最多可以装备的武器数），你拥有的武器数以及出血狗薪王的最大血量。
接下来 m 行，每行包括三个正整数 w,ATK,AS，分别代表第 i 件武器的重量、伤害和攻击时间。

输出描述:

如果能找到满足条件的 t，则输出 t，否则输出"YOU DIED"（不包含引号）。
示例1

输入

复制 
2 2 9982443
23 233 233
1 2 3

输出

复制 
YOU DIED

说明

显然，两把武器全部选择你也无法打过出血狗，狗薪王永远滴神！
示例2

输入

复制 
3 4 115
13 100 7
5 20 3
30 150 15
114 51 4

输出

复制 
7

说明

可以从四个武器中选择三个，可以选择前两个达到 18\% 负重，在最晚时刻7造成 120 的伤害击杀敌人。也可以选择第一个武器，并佩戴弗林戒指，负重 15\%，伤害提升 15\%，在时刻7造成 115 的伤害击杀敌人。

备注: