Muni zamanı#9602
Bessi Boviniyada işgüzar səfərdədir, burada -dən -ə qədər nömrələnmiş şəhər var və onlar birtərəfli hərəkətli yolla birləşdirilib. Bessi hər dəfə şəhərinə baş çəkəndə m_i muni qazanır. şəhərindən başlayaraq, Bessi şəhərlərə elə səfər etmək istəyir ki, mümkün qədər çox muni qazansın və səfərin sonunda mütləq şəhərinə qayıtmalıdır. Aydınlıq üçün qəbul edək ki, m_1 = 0.
İki şəhər arasında yol ilə hərəkət etmək bir gün çəkir. Səfərə hazırlıq baha başa gəlir: müddəti gün olan səfər c \cdot t^2 muniyə başa gəlir.
Bessi bir səfərdə maksimum nə qədər muni qazana bilər? Nəzərə alın ki, Bessi üçün şəhərindən başqa heç bir şəhərə baş çəkməmək daha sərfəli ola bilər, bu halda cavab sıfır olacaq.
Birinci sətirdə üç tam ədəd verilir: n~(2 \le n \le 1000), m~(1 \le m \le 2000) və c~(1 \le c \le 1000).
İkinci sətirdə tam ədəd m_1, m_2, \ldots, m_n~(0 \le m_i \le 1000) verilir.
Sonrakı sətirdə hər birində boşluqla ayrılmış iki tam ədəd və b~(a \ne b) verilir, bunlar şəhərindən şəhərinə birtərəfli yolu bildirir.
Bessinin bir səfərdə qazana biləcəyi maksimum muni miqdarını çıxarın.
Optimal marşrut 1 \to 2 \to 3 \to 1 \to 2 \to 3 \to 1 formasındadır. Bessi 10 + 20 + 10 + 20 = 60 muni qazanır və səfərə 1 \cdot 6^2 = 36 muni xərcləyir. Beləliklə, onun yekun mənfəəti olur.
Nümunə 1