eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Динамічна жаба

Динамічна жаба

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

У зв'язку з розширенням використання пестицидів, місцеві струмки і ріки виявилися настільки забрудненими, що стали майже неможливими для життя водних тварин.

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

Фрейд може приземлитися на кожний маленький камінь не більш ніж один раз. Великі може використовувати стільки разів, скільки забажає. У воду він стрибнути не може, оскільки вона надзвичайно забруднена.

Чи можете ви спланувати маршрут так, щоб мінімізувати максимальну відстань одного стрибка?

Вхідні дані

Перший рядок містить кількість тестів t (t < 100). Кожний тест починається двома цілими числами n (0n100) та d (1d10^9). Наступний рядок описує n камінців. Кожний камінець задається у вигляді s-m. Символ s вказує на тип камінця - Великий (B) чи Маленький (S), а m (0 < m < d) задає відстань від цього камінця до лівого берега. Камінці задаються в порядку зростання значень m.

Вихідні дані

Для кожного тесту вивести його номер та мінімально можливе значення найбільшого стрибка.

Приклад

Вхідні дані #1
3
1 10
B-5
1 10
S-5
2 10
B-3 S-6
Вихідні дані #1
Case 1: 5
Case 2: 10
Case 3: 7
Вхідні дані #2
1
6 50
S-2 B-14 S-20 S-26 B-38 S-43
Вихідні дані #2
Case 1: 18