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

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

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

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

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

Технические условия

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

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

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

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

Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 20
Сложность: 6% 17/18

Пример

Пример входных данных

3
1 10
B-5
1 10
S-5
2 10
B-3 S-6

Пример выходных данных

Case 1: 5
Case 2: 10
Case 3: 7