eolymp

Динамическая лягушка

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

Лягушка Фред находится на левом берегу такой реки. n камней расположено на прямой линии, простирающейся с левого берега на правый. Расстояние между левым и правым берегом d метров. Камни могут быть двух размеров: крупные могут выдержать любой вес, но мелкие начинают тонуть, как только на них окажется тело любой массы. Фреду нужно перейти на правый берег, где он должен собрать подарки и вернуться обратно на левый берег в свой дом.

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

Можете ли вы спланировать маршрут так, чтобы минимизировать максимальное расстояние одного прыжка?

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

Первая строка содержит количество тестов t (t < 100). Каждый тест начинается двумя целыми числами n (0n100) и d (1d109). Следующая строка описывает n камней. Каждый камень задается в виде s-m. Симол s укзывает на тип камня - Большой (B) или Маленький (S), а m (0 < m < d) определяет расстояние от этого камня до левого берега. Камни задаются в порядке возрастания значений m.

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

Для каждого теста вывести его номер и минимально возможное значение наибольшего прыжка.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3
1 10
B-5
1 10
S-5
2 10
B-3 S-6
Çıxış verilənləri #1
Case 1: 5
Case 2: 10
Case 3: 7
Giriş verilənləri #2
1
6 50
S-2 B-14 S-20 S-26 B-38 S-43
Çıxış verilənləri #2
Case 1: 18