Task about mineral water
Everyone knows that the final of the ACM 2004 programming championship was held in Prague. Besides its renowned architecture and culture, Prague is also famous worldwide for its mineral water. Despite the fact that excessive consumption of mineral water can be harmful to participants' health, many teams seized the chance to enjoy excellent mineral water at very affordable prices.
A new mineral water company, Drink Everywhere, plans to distribute its products to some of the n European cities. The artesian well is located near Prague, which we will designate as city number 1. To deliver mineral water to other cities, the company intends to use the services of the logistics company Carry Everywhere, which offers m transportation routes. Each route is defined by the cities it connects (cargo can be transported in both directions), its capacity — the number of liters of mineral water that can be transported on this route per day, and the cost of transporting mineral water on it. It might be necessary or more cost-effective to use several routes in succession or even to deliver mineral water via multiple different paths to reach some cities.
Each city is characterized by the price that local pubs and restaurants are willing to pay for a liter of mineral water. You can assume that the demand for mineral water is sufficiently high in each city, ensuring the product will always find buyers.
Drink Everywhere does not plan to sell mineral water directly in Prague due to intense competition, so for now, it aims to sell mineral water only in other cities. Help them determine the maximum profit they can achieve in one day.
Input
The first line of the input file contains the numbers n and m — the number of cities in Europe that the company is considering and the number of delivery routes, respectively. (2 ≤ n ≤ 100, 1 ≤ m ≤ 2000). The next line contains n-1 numbers — the prices of a liter of mineral water in cities 2, 3, ..., n respectively (integers not exceeding 1000).
The following m lines each contain four numbers and describe the routes. Each route is defined by the numbers of the cities it connects, its capacity, and the cost of transporting one liter of mineral water on it (capacity and cost — positive numbers not exceeding 1000).
Output
Output one number — the maximum profit the company can achieve.
Explanation of the example
The company should deliver 80 liters of mineral water to the second city (delivery via the first route will cost 50 per liter, yielding a profit of 30 per liter, totaling 2400), and 30 liters to the fourth city (the best path goes via routes 3 and 4, costing 110 per liter, yielding a profit of 20 per liter, totaling 600). Delivering more mineral water to the third city is not profitable, so the company should avoid it.