Задача про мінералку#4584
Усім відомо, що фінал чемпіонату з програмування ACM 2004 проходив у Празі. Окрім своєї знаменитої архітектури та культури, Прага також славиться на весь світ своєю мінеральною водою. Незважаючи на те, що надмірне споживання мінеральної води може завдати шкоди здоров'ю учасників, багато команд скористалися нагодою насолодитися чудовою мінеральною водою за дуже доступними цінами.
Нова компанія з виробництва мінеральної води, Drink Everywhere, планує розповсюджувати свою продукцію в деяких з європейських міст. Артезіанський колодязь розташований поблизу Праги, яку ми позначимо як місто номер . Для доставки мінеральної води в інші міста компанія має намір скористатися послугами логістичної компанії Carry Everywhere, яка пропонує транспортних маршрутів. Кожен маршрут визначається містами, які він з'єднує (вантаж можна транспортувати в обох напрямках), його пропускною здатністю — кількістю літрів мінеральної води, яку можна перевезти цим маршрутом за добу, і вартістю транспортування мінеральної води цим маршрутом. Може виникнути необхідність або бути вигідніше скористатися кількома маршрутами поспіль чи навіть доставляти мінеральну воду кількома різними шляхами, щоб дістатися до деяких міст.
Кожне місто характеризується ціною, яку місцеві паби та ресторани готові платити за літр мінеральної води. Можна вважати, що попит на мінеральну воду в кожному місті досить великий, тож продукція завжди знайде покупців.
Drink Everywhere не планує продавати мінеральну воду безпосередньо в Празі через сильну конкуренцію, тож наразі вона має намір продавати воду лише в інших містах. Допоможіть їм визначити максимальний прибуток, якого можна досягти за одну добу.
Перший рядок містить цілі числа і — кількість міст в Європі, які розглядає компанія, та кількість маршрутів доставки відповідно (2 \le n \le 100, 1 \le m \le 2000).
Другий рядок містить n-1 чисел — ціни за літр мінеральної води в містах 2, 3, \ldots, n відповідно (цілі числа, що не перевищують ).
Далі у кожному з рядків описано один маршрут чотирма числами. Кожен маршрут задається номерами двох міст, які він сполучає, його пропускною здатністю та вартістю транспортування одного літра мінеральної води цим маршрутом (пропускна здатність і вартість — додатні цілі числа, що не перевищують ).
Виведіть одне ціле число — максимальний прибуток, якого може досягти компанія.
Приклад 1
Компанія має доставити літрів мінеральної води в друге місто (доставка першим маршрутом коштує за літр, при цьому прибуток складає за літр, тобто загалом ), та літрів у четверте місто (найкращий шлях проходить маршрутами і , його вартість за літр, що дає прибуток за літр, тобто загалом ). Доставка додаткової мінеральної води в третє місто не є вигідною, тому компанія цього робити не повинна.