时间限制：1秒　　内存限制：256M

---

【题目描述】

　　奶牛们想到市区去！像你所想象的那样，他们想使得时间最短。

　　他们注意到在笔直的公路上行驶，最快的方案并不是以全速开往下一个红绿灯、刹车、等待绿灯、再加速前进．比较好的方案是在到达红灯之前减速，以便当它变成绿色的时候，还有一定的速度．已知：

　　• 公路的长度: \(L(1 ≤ L ≤ 100)\)
　　• 红绿灯的数目：\(N (0 ≤ N ≤ L + 1)\)
　　• 第 \(i\) 个红绿灯的信息：
　　　　– 位置 \(X_i(0 ≤ Xi ≤ L)\)，不同红绿灯的位置不同。
　　　　– 呈现绿色的时间: \(TG_i(1 ≤ TGi ≤ 10)\)
　　　　– 呈现红色的时间: \(TR_i(1 ≤ TRi ≤ 10)\)
　　　　– 在 0 时刻的颜色，用 R 或 G 表示红或绿
　　　　– 0 时刻时距离上次变色的时间 \(TC_i\)
　　　　其中，所有数字都是整数，红绿色灯交替出现．

　　写一个程序计算从位置 0 到位置 \(L\) 所需要的最短时间。注意：在每个离散的整数时刻汽车可以把速度提高一个单位、保持原来的速度或者降低一个单位。速度永远是非负整数。

　　开始时（0时刻），汽车处于位置 0，速度为 0，但0时刻到1时刻的单位时间内，因为需要发动汽车，汽车无法移动。结束时汽车必须处于位置 \(L\)，速度也为 0。如果遇到红灯，汽车必须停止（速度为0）。红绿灯从红色变成绿色的那一刻，可以看作绿灯；但是从绿色变成红色不可以看作绿灯。

【输入格式】

　　第 1 行：输入整数 \(L\) 和 \(N\)。
　　接下来 \(N\) 行：每行表示一个红绿灯的信息：\(X, TG, TR,R \)或 \(G,TC\)。

【输出格式】

　　从位置 0 到位置 \(L\) 的最短时间．

【输入输出样例】

　Input

4 1
1 10 10 R 0

　Output

12

【样例解释】

　　时刻9之前一直在位置0不动；
　　在时刻9把速度提高至1开始行驶，在时刻10到达位置1，此位置的红绿灯刚好变成绿灯；
　　在时刻10把速度提高至2，在时刻11到达位置3；
　　在时刻11把速度降到1，在时刻12到达位置4；
　　在时刻12把速度降到0；
　　所以，值用4秒时时间可以到达终点。

【来源】

　　Mr.he