Description

小凯从小就喜欢玩梦幻西游，但是现在小凯长大了，成为了一个穿着格子衫的高级程序员。小凯对梦幻西游有很大的情怀呀，用代码写一个游戏叫游西幻梦，但是没有很多人玩。他就想出了一个活动，在11月19日这天获得的经验值会翻5倍 。

小马是游西幻梦这个游戏为数不多的忠实爱好者，她知道了这个活动，就准备在11月19日这天大显身手。

现在小马拿出了m 个药瓶，准备开始与那些人打了。由于药瓶每个只能用一次，所以小马要谨慎的使用这些药。但是有一个问题用药量****没达到最少 打败该人所需 的属性药药量 ，则打这个人必输 。比如他用5个药去打别人，别人却表明6个药才能打过，那么相当于你输了并且这5个属性药浪费了。现在有n 个敌人，给定失败时可获得的经验、胜利时可获得的经验，打败他至少需要的药瓶数量。要求求出最大经验s ，输出5s 。

Format

Input

第一行两个数，敌人数量n 和药瓶的数量m 。

后面n 行每行三个数，分别表示失败时获得的经验li ​，胜利时获得的经验wi ​和打过敌人至少要使用的药瓶数量ui ​。

Output

一个整数，最多获得的经验的五倍(输出5s)。

Samples

6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2

1060

Hint

保证0 ≤ n，x ≤ 10^3，0 ＜ li ≤ wi ≤ 10^6，0 ≤ ui ≤ 10^3 。