题目描述

所谓“奇怪的卡车”，指的是一辆在响应客户运输请求时缺乏相应“智商”的货运卡车：它在行驶过程中不会顺路捎带中途出现的新货单，而是严格按照客户发出请求的先后顺序，一单一单地完成运输任务。

比如，原来卡车停在 1 号仓。首先 6 号仓有一批货物下单，要求从 6 号仓运到 10 号仓。此时卡车立刻出发前往 6 号仓装货。但当卡车行驶到 3 号仓附近时，另外一批货物下单，要求从 5 号仓运到 8 号仓，奇怪卡车却不会顺路去 5 号仓装货，而是必须先完成第一单：到 6 号仓装货并送到 10 号仓卸货，然后再去完成第二单：回到 5 号仓装货并送到 8 号仓卸货。

卡车由 $i$ 号仓行驶到 $i+1$ 号仓（或 $i-1$ 号仓）的时间都是 3 秒。每到达一个仓点，不管装卸多少，只要发生以下任意一种情况：

• 只有装货
• 只有卸货
• 装货和卸货同时发生 都会额外耽搁 6 秒。

PS：

1. 如果某一单货物送达并卸货后，卡车没有马上要响应的下一条请求，则卡车会在该目的仓点原地等待，这个等待过程称为 “趴窝”，且趴窝时间计入总耗时。直到下一单请求出现，卡车才从当前位置出发前往下一单的出发仓点。
2. 如果某一单卸货结束的同时，下一单的出发仓点与当前仓点相同：
   • 若此时卡车没有马上要响应的请求（也就是需要趴窝到下一单出现），则不仅要把趴窝时间计入总耗时，且下一单仍需计入装货用时 6 秒；
   • 若此时卡车有响应（说明下一单请求在之前就已经发出、正在排队等待），则视为此时“有卸有装”，装卸时间按一次处理（即符合“装货和卸货同时发生”的情况）。 现在噜噜要根据奇怪卡车接收到的 $n$ 个运输请求，编程计算奇怪卡车把所有货物运到目标仓点时总共所需要的时间。

输入格式

输入第一行包含两个整数 $x$（$1 \le x \le 100$）和 $n$（$1 \le n \le 100$），分别表示奇怪卡车开始所在的仓点编号和总共接收到的请求数目。 下面有 $n$ 行，每行包含 $3$ 个整数，依次表示：

• 该请求发出的时间$t$（单位：秒）
• 货物所在的出发仓点 $s$
• 货物将要送达的目标仓点 $e$

请求发出的时间最大为 $2000$。如果某两个请求发出的时间相同，则按照输入中的先后顺序依次处理。

输出格式

输出只包含一行一个整数，表示奇怪卡车把所有货物送到目标仓点后总共所需要的时间（从得到第一条请求时开始计算时间），单位是秒。

3 4
10 10 2
18 1 9
2 1 12
8 6 10

162

说明/提示

• 第一单从接单到卸货结束所需时间：$3 \times 2 + 6 + 3 \times 11 + 6 = 51$
• 从前一单卸货结束到第二单卸货结束所需时间：$3 \times 6 + 6 + 3 \times 4 + 6 = 42$
• 第三单从出发仓点出发到卸货结束所需时间：
  $3 \times 8 + 6 = 30$（由于出发仓点与前一单目的地相同，并且此时前一单结束时卡车有响应，所以装卸时间不必再加一次 $6$）
• 从前一单卸货结束到第四单卸货结束所需时间：$3 + 6 + 3 \times 8 + 6 = 39$ 总耗时：$51 + 42 + 30 + 39 = 162$

数据范围

$1 \le x \le 100,1 \le n \le 100, 1 \le s,e \le 10^ 7$