Всем известно, что финал чемпионата мира по программированию \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 Выведите одно число --- максимальный доход, который может получить компания. \Note Компания должна доставлять \textbf{80} литров минералки во второй город (доставка по первому маршруту будет стоить \textbf{50} за литр, доход \textbf{30} за литр, \textbf{2400} всего), и \textbf{30} литров в четвертый город (лучший путь идет по маршрутам \textbf{3} и \textbf{4}, его стоимость \textbf{110} за литр, доход \textbf{20} за литр, \textbf{600} всего). Доставлять больше минералки в третий город невыгодно, поэтому компания не должна делать этого.