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