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

Чернослив

Чернослив

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Сливочная состоит из m сливочных канав, расположенных на плоскости, и представляющих собой отрезки прямых, соединяющих между собой сливочные узлы. Сливочные канавы не пересекаются друг с другом, кроме как в сливочных узлах, которые являются концами сливочных канав. Для каждой сливочной канавы известна её пропускная способность - сколько по ней может течь единиц жидкости в единицу времени. В некотором сливочном узле t расположен общий слив сливочной. Жидкость по канаве может течь в любом направлении, но только в одном в любой конкретный момент времени.

Ясно, что канавы делят плоскость на несколько частей - рабочих площадок (внешняя часть тоже считается рабочей площадкой). Вася сейчас находится в одной из частей, на границе которой находится общий слив, но по техническим причинам не может воспользоваться сливом. Однако ему необходимо срочно организовать слив сливочного масла таким образом, чтобы масло по канавам попало в сливочный узел t. Для этого Вася собирается сливать масло в некоторый фиксированный узел s. Считается, что масло распространяется моментально, и по каждой канаве может течь единиц масла не более, чем её пропускная способность. Требуется определить, какое максимальное количество единиц масла сможет сливать Вася в единицу времени.

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

В первой строке входного файла задано число сливочных узлов n, число сливочных канав m, номер узла, которым собирается воспользоваться Вася s и номер сливочного узла с общим сливом t (1n50000, 1m3n, 1s, tn, st). Далее следуют n строк - координаты сливочных узлов x_iy_i - целые числа, не превосходящие по модулю 10^9. Никакие два сливочных узла не находятся в одной точке. Далее следуют m строк - описания сливочных канав, проведённых между сливочными узлами в виде u_jvjw_j (1u_j, v_jn, u_jv_j, 1w_j10^6), описывающих канаву между узлами u_j и v_j, имеющую целую пропускную способность w_j. Гарантируется, что канавы не пересекаются во внутренних точках, и что сливочные узлы s и t доступны со сливочной площадки, на которой находится Вася, при нормальном функционировании сливочной. Между двумя узлами находится не более одной канавы.

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

Необходимо вывести максимальное количество сливочного масла, которое может сливать Вася в единицу времени.

Пример

Входные данные #1
4 5 1 4
0 1
1 0
1 2
2 1
1 2 1000
1 3 1000
2 3 1
3 4 1000
2 4 1000
Выходные данные #1
2000