소떡소떡

그릴에 소시지 또는 가래떡 $N$개가 구워지고 있다. 그릴의 인접한 두 가로줄 사이의 거리와 인접한 두 세로줄 사이의 거리는 모두 $1$로 같고 그릴의 가로줄과 세로줄은 서로 수직이다. 그릴의 가로줄을 아래쪽부터 $1, 2, \cdot\cdot\cdot$번으로 매기고 그릴의 세로줄을 왼쪽부터 $1, 2, \cdot\cdot\cdot$번으로 매겼을 때 $i$번째 음식물은 $y\_i$번 가로줄에 나란히 놓여 있으며 $xl\_i$번부터 $xr\_i$번 세로줄에 걸쳐 있다. $i$번째 음식물의 길이는 $xr\_i - xl\_i + 1$이고 모든 음식물은 서로 겹치지 않게 놓여 있다. 그릴은 모든 음식물을 구울 수 있을 만큼 충분히 크다.

두께가 없는 꼬치 하나를 그릴의 세로줄과 겹치게 꽂아서 소떡소떡을 만들려고 한다. 소떡소떡을 만들려면 꼬치에 음식물을 1개 이상 꽂아야 하며, 음식물은 꼬치에 꽂힌 순서대로 소시지와 가래떡이 번갈아 나와야 한다. 맨 처음에 꽂는 음식물은 소시지여도 되고 가래떡이어도 된다.

소떡소떡의 크기는 꽂힌 음식물의 길이의 합과 같다. 소떡소떡의 가치는 크기에 비례하므로 만들 수 있는 가장 큰 소떡소떡을 만들려고 한다. 다만 꼬치를 만들기 전에 소시지와 가래떡 일부를 치울 수 없고, 그릴의 특정 세로줄에 있는 모든 음식물을 꽂아야 한다. 음식물을 옮기거나 새로운 음식물을 넣는 것은 허용되지 않는다.

음식물의 정보가 주어졌을 때 만들 수 있는 가장 큰 소떡소떡의 크기를 구하는 프로그램을 작성하여라.

첫 번째 줄에 소시지와 가래떡의 총 개수 $N$이 주어진다. $(1 \leq N \leq 250\,000)$

다음 $N$개의 줄에 $i$번째 음식물의 정보 $xl\_i$, $xr\_i$, $y\_i$, $t\_i$가 공백으로 구분되어 주어진다. $(1 \leq xl\_i \leq xr\_i \leq 10^9;$ $1 \leq y\_i \leq 10^9;$ $t\_i \in \{S, D\})$

$t\_i = S$이면 소시지, $t\_i = D$이면 가래떡이라는 뜻이다. $i$번째 음식물은 $y\_i$번 가로줄에 놓여 있고 $xl\_i$번부터 $xr\_i$번까지의 세로줄에 걸쳐 있다.

첫 번째 줄에 만들 수 있는 소떡소떡의 최대 크기(꽂힌 음식물의 길이 합의 최댓값)를 출력한다. 소떡소떡을 만들 수 없으면 $0$을 출력한다.