E. Байтландия, Берляндия и спорные города
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Страны Байтландия и Берляндия расположены на прямой $$$Ox$$$. Кроме этого на этой прямой расположены и спорные города, которые принадлежат каждой из стран по их мнению. Таким образом, на прямой $$$Ox$$$ расположены города трёх типов:

  • города Байтландии,
  • города Берляндии,
  • спорные города.

Недавно был запущен проект BNET — компьютерная сеть нового поколения. Теперь задача обоих государств соединить города так, чтобы сеть этой страны была связной.

Страны договорились соединить пары городов кабелями BNET таким образом, чтобы:

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

Таким образом, надо выбрать набор пар городов так, чтобы, соединив их, выполнялись оба условия одновременно. Кабели осуществляют двунаправленную передачу данных. Каждый кабель соединяет ровно два различных города.

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

Каждый город является точкой на прямой $$$Ox$$$. Технически возможно соединить города $$$a$$$ и $$$b$$$ кабелем так, что город $$$c$$$ ($$$a < c < b$$$) не подключен к этому кабелю, где $$$a$$$, $$$b$$$ и $$$c$$$ — одновременно координаты городов $$$a$$$, $$$b$$$ и $$$c$$$.

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

В первой строке записано целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^{5}$$$) — количество городов.

Далее следует $$$n$$$ строк, в каждой из которых задано целое число $$$x_i$$$ и буква $$$c_i$$$ ($$$-10^{9} \le x_i \le 10^{9}$$$) — координаты очередного города и его тип. Если город принадлежит Байтландии, то $$$c_i$$$ равно «B». Если город принадлежит Берляндии, то $$$c_i$$$ равно «R». Если город является спорным между странами, то $$$c_i$$$ равно «P».

Все города имеют различные координаты. Гарантируется, что города заданы в порядке увеличения их координат.

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

Выведите минимальную суммарную длину такого набора кабелей, что если удалить все города Берляндии ($$$c_i$$$=«R»), можно будет найти путь от любого оставшегося города до любого другого оставшегося города, двигаясь только по кабелям. Аналогично, если удалить все города Байтландии ($$$c_i$$$=«B»), можно будет найти путь от любого оставшегося города до любого другого оставшегося города, двигаясь только по кабелям.

Примеры
Входные данные
4
-5 R
0 P
3 P
7 B
Выходные данные
12
Входные данные
5
10 R
14 B
16 B
21 R
32 R
Выходные данные
24
Примечание

В первом примере нужно соединить первый город со вторым, второй с третьим, а третий с четвертым. Суммарная длина кабелей будет равна $$$5 + 3 + 4 = 12$$$.

Во втором примере нет спорных городов, поэтому нужно соединить все соседние города Байтландии и все соседние города Берляндии. Города Берляндии имеют координаты $$$10, 21, 32$$$, поэтому для их соединения нужно два кабеля длины $$$11$$$ и $$$11$$$. Города Байтландии имеют координаты $$$14$$$ и $$$16$$$, поэтому для их соединения нужен один кабель длины $$$2$$$. Таким образом, суммарная длина всех кабелей равна $$$11 + 11 + 2 = 24$$$.