Існує орієнтований граф з \(N\) вершинами та \(M\) ребрами. Вершини пронумеровані \(1, \dots, N\), а \(i\)-е ребро (\(1 \leq i \leq M\)) йде від вершини \(A_i\) до вершини \(B_i\).

Спочатку є \(X_i\) предмети на вершині \(i\) (\(1 \leq i \leq N\)), які хтось загубив.

\(K\) людей збиратимуть ці предмети. Вс \(K\) людей будуть подорожувати по графу один за іншим. Кожна людина зробить наступне.

• Починає рух з вершини 1. Потім пройде ребро будь-яку скінченну кількість разів. Для кожної відвіданої вершини (включаючи 1) зберає усі предмети на ній, якщо вони ще не зібрані.

Знайдіть максимальну загальну кількість предметів, які можна зібрати.

Формат вхідних даних

Перший рядок містить цілі числа \(N< M, K\) (\(2 \le N \le 2 \times 10^5\), \(1 \le M \le 2 \times 10^5\), \(1 \le K \le 10\))

Наступні  \(N\) рядків містять цілі числа \(A_i, B_i\) (\(1 \le A_i, B_i \le N\), \(A_i \neq B_i\), \(A_i \neq A_j\) або \(B_i \neq B_j\), якщо \(i \neq j\))

Далі рядок містить цілі числа \(X_i\) (\(1 \le X_i \le 10^9\))

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть шукану кількість предметів.

Примітка

До прикладу 1:

Двоє людей можуть зібрати 18 предметів наступним чином.

• Перша особа йде \(1 \rightarrow 2 \rightarrow 3 \rightarrow 2\) і збирає предмети на вершинах 1, 2 і 3.

• Друга особа йде \(1 \rightarrow 5\) і збирає предмети на вершині 5.

Неможливо зібрати 19 або більше предметів, тому слід вивести 18.

Приклад вхідних даних

5 5 2
1 2
2 3
3 2
1 4
1 5
1 4 5 2 8

Приклад вихідних даних

18

Приклад вхідних даних

3 1 10
2 3
1 100 100

Приклад вихідних даних

1