Sot-tteok-sot-tteok

$N$ sausages or rice cakes are being grilled. The distance between two adjacent horizontal lines and the distance between two adjacent vertical lines of the grill are both $1$, and the horizontal and vertical lines are perpendicular to each other. Number the horizontal lines $1, 2, \cdot\cdot\cdot$ from the bottom and the vertical lines $1, 2, \cdot\cdot\cdot$ from the left. The $i$-th food lies on horizontal line $y\_i$ and spans vertical lines $xl\_i$ through $xr\_i$. The length of the $i$-th food is $xr\_i - xl\_i + 1$, and no two foods overlap. The grill is large enough to grill all of the foods.

You want to make a sot-tteok-sot-tteok by threading one skewer of zero thickness along a vertical line of the grill. The skewer must hold at least one food, and the foods on it must alternate between sausage and rice cake in the order they are threaded. The first food may be either a sausage or a rice cake.

The size of your skewer is the sum of the lengths of the foods on it. Since the value grows with the size, you want the largest possible skewer. However, you cannot remove any sausages or rice cakes before making the skewer. You must thread every food that lies on one particular vertical line of the grill. You may not move foods or add new ones.

Write a program that takes the food information and prints the largest skewer you can make.

The first line contains $N$, the total number of sausages and rice cakes. $(1 \leq N \leq 250\,000)$

Each of the next $N$ lines contains $xl\_i$, $xr\_i$, $y\_i$, and $t\_i$ for the $i$-th food, separated by spaces. $(1 \leq xl\_i \leq xr\_i \leq 10^9;$ $1 \leq y\_i \leq 10^9;$ $t\_i \in \{S, D\})$

If $t\_i = S$, the food is a sausage. If $t\_i = D$, the food is a rice cake. The $i$-th food lies on horizontal line $y\_i$ and spans vertical lines $xl\_i$ through $xr\_i$.

On the first line, print the maximum size of a sot-tteok-sot-tteok you can make, which is the largest sum of the lengths of the threaded foods. If you cannot make one, print $0$.