Неориентированный связный граф без петель и кратных рёбер называется кактусом тогда и только тогда, когда каждое его ребро принадлежит не более чем одному простому циклу. Простым называется цикл без повторяющихся вершин.

Даны $n$ точек на плоскости; координаты $i$-й точки равны $(x_i,y_i)$. Также даны $m$ рёбер; $i$-е ребро соединяет вершины $u_i,v_i$. Гарантируется, что неориентированный граф, образованный этими $n$ точками и $m$ рёбрами, является кактусом.

Изначально все $m$ рёбер белые. Можно выбрать несколько рёбер и покрасить их в чёрный цвет. Стоимость покраски $i$-го ребра в чёрный цвет равна $w_i$.

Для каждой пары разноцветных рёбер с общей вершиной пусть, начав с белого ребра и поворачиваясь вокруг общей вершины против часовой стрелки, нужно пройти $x$ рёбер, чтобы достичь чёрного ребра. Тогда эта пара даёт $p\times x$ единиц энергии. В частности, для двух коллинеарных рёбер одного направления (то есть рёбер, у которых другие вершины имеют одинаковый полярный угол относительно общей вершины) считается, что раньше достигается ребро с меньшим номером; иначе говоря, у ребра с меньшим номером полярный угол меньше.

Найдите максимальное значение суммы полученной после покраски энергии за вычетом суммарной стоимости покраски.

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

Данные считываются из файла color.in.

Первая строка содержит три положительных целых числа $n,m,p$ — число вершин, число рёбер и коэффициент получения энергии соответственно.

Следующие $m$ строк содержат по три целых числа $u_i,v_i,w_i$, задающих концы и стоимость $i$-го ребра.

Следующие $n$ строк содержат по два целых числа $x_i,y_i$ — координаты $i$-й точки.

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

Выведите ответ в файл color.out.

Выведите в одной строке одно целое число — максимальное значение суммы полученной после покраски энергии за вычетом суммарной стоимости покраски.

Примеры

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

5 4 10
1 4 1
2 3 2
3 4 2
3 5 2
0 1
1 1
0 0
1 0
2 0

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

38

Примечание

На рисунке ниже чёрными сплошными линиями показаны рёбра, покрашенные в чёрный цвет, а серыми пунктирными линиями — рёбра, оставшиеся белыми.

После покраски ребра $(3,4)$ в чёрный цвет за $2$ единицы стоимости от ребра $(1,4)$ можно достичь $(3,4)$, пройдя $1$ ребро против часовой стрелки вокруг вершины $4$, и получить $10\times1=10$ единиц энергии. От ребра $(2,3)$ можно достичь $(3,4)$, пройдя $1$ ребро против часовой стрелки вокруг вершины $3$ (обратите внимание: согласно правилу из условия, сначала достигается $(3,4)$, а затем $(3,5)$), и получить $10\times1=10$ единиц энергии. От ребра $(3,5)$ можно достичь $(3,4)$, пройдя $2$ ребра против часовой стрелки вокруг вершины $3$, и получить $10\times2=20$ единиц энергии. Таким образом, суммарная полученная энергия равна $10+10+20=40$, суммарная стоимость равна $2$, и искомый максимум равен $40-2=38$. Можно доказать, что раскраски с большим ответом не существует.

Пример 2

См. файлы color/color2.in и color/color2.ans в каталоге участника.

Подзадачи

Для всех тестовых данных гарантируется:

• $2\le n,m\le2\times10^5$, $1\le p\le1000$;
• $\forall 1\le i\le m,\ 1\le u_i,v_i\le n,\ 0\le w_i\le10^4$;
• $\forall 1\le i\le n,\ 0\le x_i,y_i\le10^7$;
• данный граф является кактусом;
• координаты любых двух точек различны.

Особое свойство A: гарантируется $m=n-1$, то есть данный граф является деревом.

Особое свойство B: гарантируется, что любые два ребра данного графа без общей вершины не пересекаются на плоскости, то есть дано плоское вложение графа.

Особое свойство C: гарантируется $\forall 1\le i\le m,\ w_i=0$.

Особое свойство D: гарантируется $\forall 1\le i\le m,\ w_i=1$, $p=1$.