도시 출장

지영은 보비니아에서 출장 업무를 하고 있습니다. 보비니아에는 $N$ ($2 \le N \le 1000$)의 도시가 있으며 이 도시들은 $1 \ldots N$으로 표시된 $M$ ($1 \le M \le 2000$)개의 일방통행 도로로 연결되어 있습니다. 

지영이도시 $i$를 방문할 때마다  $m_i$ 원 ($0 \le m_i \le 1000$)를 얻습니다. 도시 1에서 시작하여 도시 1로 다시 돌아오면서 최대한 많은 원화를 버는 것이 지영의 목표입니다. 혼란을 피하기 위해 $m_1=0$라고 합시다.

두 도시 사이를 도로를 통해 이동하는데 하루가 걸리며, 여행을 준비에는 비용이 많이 듭니다.

$T$일 동안 여행하는데는 $C \cdot T^2$ 원이 필요합니다 ($1 \le C \le 1000$).

지영가 한 번의 여행에서 벌 수 있는 원화의 최대 금액은 얼마인가요? 

주의할 점은 지영이 도시 1을 제외한 다른 도시를 방문하지 않는 것이 최적의 선택일 수도 있으며, 이 경우 답은 0이 됩니다.

첫 번째 줄에는 세 개의 정수 $N$, $M$, $C$가 포함되어 있습니다.

두 번째 줄에는 $N$개의 정수 $m_1,m_2, \ldots m_N$이 포함되어 있습니다.

다음 $M$개의 줄은 각각 두 개의 공백으로 구분된 정수 $a$와 $b$ ($a \neq b$)를 포함하고 있으며, 이는 도시 $a$에서 도시 $b$로 향하는 일방통행 도로를 나타냅니다.