Il Tempo dei Muny#9602
Bessie è in viaggio d'affari in Bovinia, dove ci sono città, numerate da a e collegate da strade a senso unico. Ogni volta che Bessie visita la città , guadagna m_i muny. Partendo dalla città , Bessie vuole visitare le città in modo da guadagnare quanti più muny possibile, e alla fine deve tornare alla città . Per chiarezza, assumiamo che m_1 = 0.
Spostarsi tra due città lungo una strada richiede un giorno. Organizzare il viaggio è costoso: un viaggio di durata giorni costa c \cdot t^2 muny.
Qual è il massimo numero di muny che Bessie può guadagnare in un solo viaggio? Si noti che potrebbe risultare più conveniente per Bessie non visitare affatto altre città oltre alla città , nel qual caso la risposta sarà zero.
La prima riga contiene tre numeri interi: n~(2 \le n \le 1000), m~(1 \le m \le 2000) e c~(1 \le c \le 1000).
La seconda riga contiene numeri interi m_1, m_2, \ldots, m_n~(0 \le m_i \le 1000).
Le successive righe contengono due numeri interi separati da uno spazio, e b~(a \ne b), che indicano una strada a senso unico dalla città alla città .
Stampa il numero massimo di muny che Bessie può guadagnare in un solo viaggio.
Il percorso ottimale è 1 \to 2 \to 3 \to 1 \to 2 \to 3 \to 1. Bessie guadagna 10 + 20 + 10 + 20 = 60 muny e spende 1 \cdot 6^2 = 36 muny per il viaggio. Il suo profitto finale è quindi .
Esempio 1