F. Новый год и радужные развилки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Роя и Бива есть множество из n точек на бесконечной числовой прямой.

Каждая точка имеет один из трех цветов: красный, зеленый или синий.

Рой и Бив хотят соединить все точки несколькими линиями. Линии могут быть проведены между любой парой данных точек. Стоимость линии равна расстоянию между точками, которые она соединяет.

Рой и Бив хотят провести линии так, чтобы они оба видели, что все точки соединены (напрямую или через несколько линий).

Однако, не все так просто: Рой не видит красный цвет, а Бив — синий.

Поэтому они хотят выбрать линии так, что если убрать все красные точки, то оставшиеся синие и зеленые точки будут соединены, и, аналогично, если убрать все синие точки, то оставшиеся красные и зеленые точки будут соединены.

Вычислите минимальную суммарную стоимость набора линий, который удовлетворяет вышеприведенным ограничениям.

Входные данные

Первая строка содержит целое число n (1 ≤ n ≤ 300 000) — количество точек.

Следующие n строк содержат по два объекта pi и ci (pi — целое число, 1 ≤ pi ≤ 109, ci — заглавная буква латинского алфавита «R», «G» или «B») — позиция i-й точки и цвет i-й точки. «R» обозначает красный цвет, «G» — зеленый, а «B» — синий. Позиции даны в строго возрастающем порядке.

Выходные данные

Выведите одно целое число: минимальную стоимость подходящего набора линий.

Примеры
Входные данные
4
1 G
5 R
10 B
15 G
Выходные данные
23
Входные данные
4
1 G
2 R
3 B
10 G
Выходные данные
12
Примечание

В первом тесте из условия оптимально нарисовать линии между точками (1,2), (1,4), (3,4). Их стоимости равны 4, 14, 5, соответственно.