Динамічна жаба
Динамічна жаба
У зв'язку з розширенням використання пестицидів, місцеві струмки і ріки виявилися настільки забрудненими, що стали майже неможливими для життя водних тварин.
Жаба Фред знаходиться на лівому березі такої річки. 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.
Вихідні дані
Для кожного тесту вивести його номер та мінімально можливе значення найбільшого стрибка.
Приклад
3 1 10 B-5 1 10 S-5 2 10 B-3 S-6
Case 1: 5 Case 2: 10 Case 3: 7
1 6 50 S-2 B-14 S-20 S-26 B-38 S-43
Case 1: 18