Неорієнтований зв’язний граф без петель і кратних ребер називається кактусом тоді й лише тоді, коли кожне його ребро належить не більш ніж одному простому циклу. Простий цикл — це цикл, у якому вершини не повторюються.

Кактус; не кактус (середнє ребро належить двом циклам); не кактус (граф незв’язний).

На площині задано $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$ рядків містять по три цілі числа. У $i$-му з них записано $u_i,v_i,w_i$ — кінці та вартість $i$-го ребра.

Наступні $n$ рядків містять по два цілі числа. У $i$-му з них записано $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

Пояснення

На рисунку нижче чорні суцільні лінії позначають ребра, пофарбовані в чорний колір, а сірі пунктирні — ребра, які залишилися білими.

Витратимо $2$, щоб пофарбувати ребро $(3,4)$ у чорний колір. Від ребра $(1,4)$, обертаючись навколо вершини $4$ проти годинникової стрілки, через $1$ ребро можна досягти $(3,4)$ та отримати $10\times 1=10$ енергії. Від $(2,3)$, обертаючись навколо вершини $3$ проти годинникової стрілки, через $1$ ребро можна досягти $(3,4)$ (зауважте: згідно з правилом в умові спочатку досягається $(3,4)$, а потім $(3,5)$) та отримати $10\times 1=10$ енергії. Від $(3,5)$, обертаючись навколо вершини $3$ проти годинникової стрілки, через $2$ ребра можна досягти $(3,4)$ та отримати $10\times 2=20$ енергії. Отже, сумарна енергія після фарбування становить $10+10+20=40$, сумарна вартість — $2$, а шуканий максимум дорівнює $40-2=38$.

Можна довести, що способу фарбування з більшою відповіддю не існує.

Приклад 2

Див. файли color/color2.in та color/color2.ans у каталозі учасника.

Підзадачі

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

• $2\le n,m\le 2\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$.