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

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

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

• Время путешествия Tij для всех дорог
• Длительность обоих цветов на перекрестке i: DBi (1 ≤ DBi ≤ 100) для синего цвета и DPi (1 ≤ DPi ≤ 100) для фиолетового
• Начальный цвет Ci светофора на перекрестке i (буква 'B' или 'P' соответствующего значения) и оставшееся время Ri (1 ≤ Ri ≤ 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 символом и тремя целыми числами: Ci, Ri, DBi и DPi.

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

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

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