Time is Mooney

Bessie는 Bovinia에서 출장을 다닌다. Bovinia에는 $N$개의 도시가 있고 ($2\le N\le 1000$), 각 도시에는 $1$부터 $N$까지 번호가 붙어 있다. 도시들은 $M$개의 일방통행 도로로 연결되어 있다 ($1\le M\le 2000$). Bessie가 도시 $i$를 방문할 때마다 $m_i$ moonies를 번다 ($0\le m_i\le 1000$). Bessie는 도시 1에서 출발해 최대한 많은 moonies를 벌기 위해 여러 도시를 방문하고, 도시 1로 돌아오려 한다. 혼동을 피하기 위해 $m_1=0$이다.

도로를 따라 두 도시 사이를 이동하는 데는 하루가 걸린다. 여행 준비에는 비용이 많이 든다. $T$일 동안 여행하려면 $C\cdot T^2$ moonies가 든다 ($1\le C\le 1000$).

Bessie가 한 번의 여행으로 벌 수 있는 moonies의 최댓값은 얼마인가? 도시 1 외에는 아무 도시도 방문하지 않는 것이 최적일 수도 있으며, 이때 답은 0이다.

첫째 줄에 세 정수 $N$, $M$, $C$가 주어진다.

둘째 줄에 $N$개의 정수 $m_1,m_2,\ldots m_N$이 주어진다.

다음 $M$개의 줄에는 도시 $a$에서 도시 $b$로 가는 일방통행 도로를 나타내는 두 정수 $a$와 $b$가 공백으로 구분되어 주어진다 ($a\neq b$).

답을 한 줄에 출력한다.

최적의 여행 경로는 $1\to 2\to 3 \to 1\to 2\to 3\to 1$이다. Bessie는 $10+20+10+20-1\cdot 6^2=24$ moonies를 번다.