Maximizing Water Delivery

On planet X, there are many settlements and water towers arranged in two parallel horizontal lines. The settlements are on the north side and are numbered from 1 to \(N\) from west to east; the towers are on the south side and are numbered from 1 to \(N\) from west to east. Each tower is connected by a vertical water pipe (powered with pumps) to the settlement directly above it. In addition to these \(N\) vertical pipes, there are \(M\) one‐way horizontal pipelines. Each horizontal pipeline connects two adjacent vertical lines at a given height \(y\). Specifically, a horizontal pipeline is given by a triple \( (X_i, Y_i, d) \) where:

• If \(d=R\) (rightward), the pipe connects point \((X_i, Y_i)\) to \((X_i+1, Y_i)\);
• If \(d=L\) (leftward), it connects \((X_i, Y_i)\) to \((X_i-1, Y_i)\).

Water flows upward continuously along each vertical pipe. At any moment, if the water reaches a point where a horizontal pipe starts (and if the water has not yet passed that height), it may follow that horizontal pipe in its specified direction, then continue upward in the new column. Note that along any path, the sequence of used horizontal pipelines must have strictly increasing \(y\) values (since water flows upward).

Now Pear plans to build one additional horizontal pipeline. To simplify matters, the new pipeline must be horizontal and one‐way going from left to right – that is, it will connect some point in column \(t\) to the point immediately to its right in column \(t+1\) at some chosen \(y\) (which need not be an integer). This new pipeline may overlap existing ones. After adding the new pipeline, for each water tower \(i\) (located at column \(i\)), let \(A_i\) be the number of settlements (i.e. vertical columns) that can be reached via a path. Pear’s goal is to choose the extra pipeline (its position and its \(y\)-coordinate) so that the sum \(A_1+A_2+\cdots +A_N\) is maximized.

Your task is to compute the maximum possible total number of reachable settlements from all water towers after optimally adding the extra pipeline.

Note: Vertically, water always flows from \(y=0\) (the tower) to \(y=K\) (the settlement) for some \(K\) (constant and sufficiently high). Therefore, a horizontal pipe is usable if the water reaches its \(y\)-coordinate. In each adjacent pair of columns, there may be several horizontal pipes; however, along any valid path the \(y\) values of used pipes must form a strictly increasing sequence. The extra pipeline (which is rightward) can be inserted on any adjacent pair of columns (i.e. between columns \(t\) and \(t+1\) for some \(1 \le t < N\)) and you may choose its \(y\) arbitrarily (even non‐integer), so as to achieve the maximum delivery.

The optimal solution may involve using the new pipeline to lower the threshold at which water can cross between two columns. In other words, by placing the extra pipeline at a very small \(y\) (but greater than 0) on a selected adjacent pair, water coming from the lower parts of the vertical pipe can make the transition and thus possibly join a longer chain.

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of water towers/settlements and the number of existing horizontal pipelines). Each of the next \(M\) lines contains a number \(X\), a real number \(Y\) and a character \(d\). If \(d\) is R then the pipeline is rightward and connects \((X, Y)\) to \((X+1, Y)\); if L then it is leftward and connects \((X, Y)\) to \((X-1, Y)\).

You may assume that in each adjacent pair there is at most one pipeline with the same \(y\)-coordinate.

outputFormat

Output a single integer — the maximum sum \(A_1+ A_2+\cdots +A_N\), where \(A_i\) is the number of settlements reachable from the \(i\)th water tower after optimally adding one extra rightward horizontal pipeline.

sample

3 0

4