题目描述

最近小王所在的城市在修建地铁，已经有很多的地铁已经完工，但也有一些还在施工中。现在小王要出发去参加朋友的聚会，在出行时会尽可能的节省时间，地铁的速度非常快。乘地铁每公里只需 $3$ 分钟，步行的话每公里需要 $20$ 分钟。

小王从家里出发，通过导航发现，到达目的地有 $n$ 条路，从导航来看到达每个目的地的时间都差不多，但是导航的数据并未实时更新，有些地方在修建地铁所以走不通，需要绕远路，绕路每公里需要 $30$ 分钟。

如果时间足够的话，小王可以慢慢计算哪一条最快，可惜聚会就要开始了，小王不得不选取一条导航显示最快的一条。

• 如果 $i$ 号点有地铁已完工，那么可以从 $i - 1$ 号点乘地铁到 $i$ 号点；
• 如果 $i$ 号点有地铁未完工，那么可以从 $i - 1$ 号点绕远路到 $i$ 号点；
• 如果 $i$ 号点没有地铁，那么可以从 $i - 1$ 号点步行到 $i$ 号点；

输入格式

第一行输入 $L，M$。分别表示所选道路的长度和道路中地铁的数量；

接下来 $M$ 行，为每个地铁的信息，每行 $3$ 个数 $x，l，r$。分别表示 地铁是否在完工（$0$ 未完工 ，$1$ 已完工），$l ，r$ 表示地铁的范围；

输出格式

输出到达目的的时间；

样例

50 3
1 1 20
0 21 30
1 40 50

573

提示

样例 1 解析

小王处在 $0$ 的位置 ， 坐地铁到 $20$ ，路径 $20$ 公里 ，共耗时 $20 \times 3 = 60$；

小王处在 $20$ 的位置 ， 中间修地铁，绕路 $10$ 公里到 $30$ 的位置， 共耗时 $10 \times 30 + 60 = 360$；

小王处在 $30$ 的位置， 步行到 $39$ 的位置，路径 $9$ 公里 ，共耗时 $9 \times 20 + 360 = 540$；

小王处在 $39$ 的位置， 坐地铁到 $50$ ，路径 $11$ 公里 ， 共耗时 $11 \times 3 + 540 = 573$；

数据范围

$20\%$ 的数据满足，$L ≤ 100 , M ＜ 100$ ， 地铁不会有重叠部分（边缘也不会）；

$50\%$ 的数据满足，$L ≤ 10000 ， M ＜ 10000$ ，地铁不会有重叠部分（边缘也不会）；

$70\%$ 的数据满足，$L ≤ 100000 , M ＜ 100000$ ， 地铁不会有重叠部分（边缘也不会） ；

额外 $10\%$ 的数据满足，$L ≤ 10000 ，M ＜ 10000$ ，地铁有重叠部分，只要存在有地铁部分就可以坐地铁；

额外 $20\%$ 的数据满足，$L ≤ 100000 ，M ＜ 100000$ ，地铁有重叠部分，只要存在有地铁部分就可以坐地铁；

$l$ 的下标可能为 $0$。