Sunday Drive
После напряженного участия в программном конкурсе в субботу, вы хотите расслабиться, совершив неспешную поездку в воскресенье. Однако бензин сейчас очень дорогой! Может быть, если вы будете креативно менять полосы, то сможете минимизировать пройденное расстояние и сэкономить немного денег!
Вам будет предоставлено описание нескольких участков шоссе. Все участки имеют одинаковое количество полос. Представьте, что ваша машина — это точечная масса, движущаяся по центру полосы. Каждая полоса имеет ширину 10 футов. Существует два типа участков шоссе: изогнутые и прямые. Вы можете менять полосы только на прямых участках, и для перехода на одну полосу требуется минимум 100 футов прямого участка. Конечно, вы можете потратить больше времени, если захотите.
Все изогнутые участки делают повороты на 90 градусов. Вы не можете менять полосы на изогнутом участке. Кроме того, вы должны двигаться точно по середине полосы во время поворота. Таким образом, во время поворота ваше положение будет 5 футов, или 15 футов, или 25 футов от края и так далее.
Имея описание шоссе, вычислите минимальное общее расстояние, необходимое для проезда по всему шоссе, включая повороты и смену полос. Вы можете начать и закончить в любой полосе по вашему выбору. Предположим, что ваша машина — это точечная масса в центре полосы. Шоссе может пересекаться само с собой, но изменения в высоте незначительны, так что не стоит беспокоиться об их влиянии на пройденное расстояние.
Чтобы использовать прямой участок для пересечения 2 полос, этот участок должен быть длиной не менее 200 футов.
Входные данные
Входные данные содержат несколько тестовых случаев. Каждый тестовый случай начинается с двух целых чисел
N M
где N (1 ≤ N ≤ 1,000) — количество сегментов, а M (2 ≤ M ≤ 10) — количество полос.
На каждой из следующих N строк будет описание сегмента, состоящее из буквы и числа, разделенных одним пробелом:
T K
Буква T — одна из S, L или R (всегда заглавная). Это указывает на тип участка: прямой участок (S), левый поворот (L) или правый поворот (R). Если участок прямой, то число K (10 ≤ K ≤ 10,000) — это просто его длина в футах. Если участок — правый или левый поворот, то число K (10 ≤ K ≤ 10,000) — это радиус внутреннего края шоссе, также в футах. Входные данные никогда не будут содержать последовательных прямых участков, но возможны несколько последовательных поворотов. Входные данные заканчиваются строкой с двумя 0.
Выходные данные
Для каждого тестового случая выведите одно число в отдельной строке, указывающее минимальное расстояние (в футах), необходимое для проезда по всему шоссе. Число должно быть выведено с точностью до двух десятичных знаков, округленное. Не выводите лишние пробелы и не разделяйте ответы пустыми строками.