eolymp
bolt
Try our new interface for solving problems
Problems

Задача про минералку

Задача про минералку

Time limit 1 second
Memory limit 64 MiB

Всем известно, что финал чемпионата мира по программированию ACM 2004 проходил в Праге. Помимо своей известной архитектуры и культуры, Прага всемирно известна за свою минералку. Несмотря на то, что чрезмерное употребление минералки вредит здоровью участников, многие команды воспользовались возможностью попробовать отличную минералку по самым дешевым ценам.

Новая компания-проиводитель минералки Пейте везде планирует распространять свою продукцию в некоторых изn европейских городов. Собственно артезианская скважина расположена около Праги, которой, конечно, мы присвоим номер 1. Для доставки минералки в другие города компания планирует воспользоваться услугами логистической компании Вози везде, которая предлагает m маршрутов для перевозки грузов. Каждый маршрут задается номерами городов, которые он соединяет (грузы можно возить в обоих направлениях), его пропускной способностью — количеством литров минералки, которые могут быть преревезены по этому маршруту за один день, и стоимостью перевозки минералки по нему. Вполне может оказаться так, что для доставки минералки в некоторые города может потребоваться (или быть выгодно) использовать несколько маршрутов один за другим или даже доставлять минералку по нескольким разным путям.

В свою очередь, каждый город характеризуется ценой, по которой местные пабы и рестораны готовы платить за литр минералки. Вы можете считать, что спрос на минералку достаточно неограничен в каждом городе, то есть продукт всегда найдет своего покупателя.

Пейте везде пока не планирует продавать минералку непосредственно в Праге, так как там очень высока конкуренция, поэтому пока она планирует только продавать минералку в некоторых других городах. Помогите им определить, какую максимальную прибыль они могут получить за один день.

Input data

В первой строке входного файла находятся числа n и m — число городов в Европе, которые рассматривает компания и количество маршрутов доставки соответственно. (2n100, 1m2000). В следующей строке находится n-1 число — цены литра минералки в городах 2, 3, ..., n соответственно (целые числа не превосходящие 1000).

Следующие m строк одержат по четыре числа каждая и описывают маршруты. Каждый маршрут задается номерами городов, которые он соединяет, его пропускной способностью и ценой перевозки одного литра минералки вдоль него (пропускная способность и цена — положительные числа, не превосходящие 1000).

Output data

Выведите одно число — максимальный доход, который может получить компания.

Examples

Input example #1
4 4
80 50 130
1 2 80 50
2 4 40 90
3 1 40 60
3 4 30 50
Output example #1
3000

Note

Компания должна доставлять 80 литров минералки во второй город (доставка по первому маршруту будет стоить 50 за литр, доход 30 за литр, 2400 всего), и 30 литров в четвертый город (лучший путь идет по маршрутам 3 и 4, его стоимость 110 за литр, доход 20 за литр, 600 всего). Доставлять больше минералки в третий город невыгодно, поэтому компания не должна делать этого.