Светофоры

Кеноша - город около Фермера Джона, имеет m дорог (пронумерованных 1..m), которые соединяют n перекрестков (пронумерованных 1..n). Никакие две дороги не соединяют одну и ту же пару перекрестков. Никакая дорога не соединяет перекресток сам с собой. Время путешествия T[ij] (1 ≤ T[ij] ≤ 100) между перекрестками i и j одно и то же в обоих направлениях (то есть T[ij] = T[ji]).

Каждый перекресток имеет один светофор с двумя цветами: синим или фиолетовым. Цвет каждого света периодически чередуется: синий некоторое время, а затем фиолетовый некоторое другое время. Движение по дороге между любыми двумя перекрестками разрешается начать, если только огни светофоров на обоих перекрестках имеют один цвет в момент отправления от одного перекрестка к другому. Цвета светофоров не обязательно должны быть одинаковыми во время всей поездки по дороге.

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

• Время путешествия T[ij] для всех дорог

• Длительность обоих цветов на перекрестке i: DB[i] (1 ≤ DB[i] ≤ 100) для синего цвета и DP[i] (1 ≤ DP[i] ≤ 100) для фиолетового

• Начальный цвет C[i] светофора на перекрестке i (буква 'B' или 'P' соответствующего значения) и оставшееся время R[i] (1 ≤ R[i] ≤ 100) до изменения цвета

Найдите наименьшее время, через которое можно попасть из перекрестка s (1 ≤ s ≤ n) в перекресток d (1 ≤ d ≤ n, d ≠ s).

Рассмотрим карту с четырьмя перекрестками и пятью дорогами. Фермер Джон хочет попасть из перекрестка 1 на перекресток 4. Цвет на первом перекрестке синий, на остальных фиолетовый.

Наименьшее время равно 127, используя путь 1-2-4.

Initially, the light at junction 1 is blue. Since the light at junction 2 is purple, vehicle waits at junction 1 for 2 seconds then travels 4 seconds to junction 2.

At time 6, the light at junction 2 switches to blue whereas the light at junction 4 has 32 more seconds to switch to blue. However, after 32 seconds, the light at junction 2 switches to purple and the light at junction 4 switches to blue at the same time. So the vehicle needs to wait 13 seconds more for junction 2 to switch to blue then the lights have the same color and vehicle travels 76 seconds to the destination junction 4.

Общее время 2 + 4 + 32 + 13 + 76 = 127 секунд.

Ниже представлен план путешествия:

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

Первая строка содержит два целых числа s и d.

Вторая строка содержит два целых числа n (2 ≤ n ≤ 300) и m (1 ≤ m ≤ 14000).

i-ая из следующих n строк описывает перекресток i символом и тремя целыми числами: C[i], R[i], DB[i] и DP[i].

k-ая из следующих m строк описывает дорогу k тремя целыми числами i, j и T[ij].

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

Print the time taken by a minimum-time path from the source junction to the destination junction. If there is no path, output 0.

Примеры