Merchant#224
A merchant owns three types of goods: diamonds, apples, and silk. For each product, the unit price (in gold coins per unit weight) and the available quantity are known.
There are cities in the country, numbered from to . The merchant's hometown is city , and the capital is city . To sell his goods in the capital, the merchant must travel along a certain route that may pass through other cities. Some pairs of cities are connected by roads, and traveling a road costs a certain amount of gold. Each city imposes a tax on each type of good he carries through, calculated as a percentage of the product's value. Once the merchant leaves a city, he cannot return. Each pair of cities is connected by at most one road.
The merchant wants to maximize his profit, defined as the difference between the total revenue obtained from selling goods in the capital and the expenses spent during the journey. He does not have to take all of his goods. The merchant always has enough gold to pay taxes and may not pay with goods being carried to the capital. All roads are one-way.
The first line contains two integers (2 \leq N \leq 500) and (M \geq 1): the number of cities and the number of roads.
The second line contains three non-negative integers: the quantities of diamonds, apples, and silk owned by the merchant.
The third line contains three non-negative integers: the unit prices (in gold) of diamonds, apples, and silk in the capital.
Each of the next N-2 lines (lines to N+1) contains three integers from to , denoting the percentage tax for diamonds, apples, and silk in cities to N-1. Cities and do not levy taxes.
The next lines each contain three non-negative integers: the first two integers specify a pair of cities (from to ) connected by a one-way road, and the third integer gives the travel cost for this road. Roads go from the first city listed to the second. The quantities of goods, their prices, and the travel costs do not exceed .
Print a single number: the exact maximum profit obtainable from traveling to the capital. The answer must always be given with exactly two decimal places. If the merchant cannot make a profit or cannot reach the capital through the given roads, output 0.00.
Example 1