Усім відомо, що фінал чемпіонату світу по програмуванню \textit{\textbf{ACM 2004}} проходив у Празі. Крім своєї відомої архітектури та культури, Прага всесвітньо відома через свою мінералку. Не дивлячись на те, що понадмірне вживання мінералки школить здоров'ю участників, багато команд скористались можливітю покуштувати відмінну мінералку по самим дешевим цінам. Нова компанія-виробник мінералки \textit{Пийте скрізь} планує поширювати свою продукцію у деяких з \textbf{n} європейських міст. Власне сама артезіанська скважина розміщена поблизу Праги, якій, звичайно ж, ми присвоїмо номер \textbf{1}. Для доставки мінералки у інші міста компанія планує скористатись послугами логістичної компанії \textit{Вози скрізь}, яка пропонує \textbf{m} маршрутів для перевезення вантажів. Кожен маршрут задається номерами міст, які він з'єднує (вантажі можна возити у обох напрямках), його пропускною здатністю --- кількістю літрів мінералки, які можутб бути преревезені цим маршрутом за один день, та вартістю перевезення мінералки по ньому. Цілком може статись так, що для доставки мінералки у деякі міста може знадобитись (або бути вигідним) використовувати декілька маршрутів один за одним або навіть доставляти мінералку по декільком різним шляхам. У свою чергу, кожне місто характеризується ціною, яку місцеві паби і ресторани готові платити за літр мінералки. Ви можете вважати, що попит на мінералку достатотньо необмежений у кожному місті, тобто продукт завжди знайде свого покупця. \textit{Пийте скрізь} поки не планиує продавати мінералку безпосередньо у Празі, так як там дуже велика конкуренція, тому поки вона планує лише продавати мінералку у деяких інших містах. Допомоєіть їм визначити, який максимальний прибуток вони можуть отримати за один день. \InputFile У першому рядку вхідного файлу знаходяться числа \textbf{n} і \textbf{m} --- кількість міст у Європі, які розглядає компанія і кількість маршрутів доставки відповідно. (\textbf{2} ≤ \textbf{n} ≤ \textbf{100}, \textbf{1} ≤ \textbf{m} ≤ \textbf{2000}). У наступному рядку знаходяться \textbf{n-1} чисел --- ціни літра мінералки у містах \textbf{2}, \textbf{3}, ..., \textbf{n} відповідно (цілі числа, які не перевищують \textbf{1000}). Наступні \textbf{m} рядків містять по чотири числа у кожному і описують маршрути. Кожен маршрут задається номерами міст, які він з'єднує, його пропускною здатністю та ціною перевезення одного літра мінералки по ньому (пропускна здатність і ціна --- додатні числа, які не перевищують \textbf{1000}). \OutputFile Виведіть одне число --- максимальний прибуток, який зможе отримати компанія. \textbf{Пояснення до прикладу} Компанія повинна доставляти \textbf{80} літрів мінералки у друге місто (доставка по першому маршруту буде коштувати \textbf{50} за літр, прибуток \textbf{30} за лутр, \textbf{2400} усього), і \textbf{30} літрів у четверте місто (кращий шлях йде по маршрутам \textbf{3} та \textbf{4}, його вартість \textbf{110} за літр, прибуток \textbf{20} за літр, \textbf{600} усього). Доставляти більше мінералки у третє місто невигідно, тому компанія не повинна робити цього.