Minimizing Payment with Sequential Discounts

A small store offers a very simple and interesting promotion: during a single shopping trip, if you purchase product \(A\) then you can buy product \(B\) at a discounted price of \(P\) per unit (with no limit on the quantity of \(B\)). For example, if you buy premium oil, you can then purchase soap at \(2.00\) yuan per piece; if you buy soap, you can purchase cola at \(1.50\) yuan per can; and so on.

You are given the original prices for all products along with a set of discount offers and a list of required products (each product is to be purchased exactly once). Note that the discount offer is only applied if the product granting the discount is purchased before the discounted product. Your task is to choose the optimal order of purchasing the required products so as to minimize the total cost. Even if buying extra items might reduce the cost, you are not allowed to purchase products that are not required.

Input: The first line contains two integers \(n\) and \(m\): the total number of products (numbered from \(1\) to \(n\)) and the number of discount offers, respectively. The second line contains \(n\) floating-point numbers, where the \(i^{th}\) number is the original price of product \(i\). The next \(m\) lines each contain two integers and a floating-point number \(A\), \(B\), and \(P\), meaning that if you purchase product \(A\), then you can buy product \(B\) at a discounted price of \(P\) per unit.

The next line contains an integer \(k\), the number of required products. The final line contains \(k\) distinct integers indicating the product numbers that you must purchase.

inputFormat

The input format is as follows:

• The first line contains two integers (n) and (m), the total number of products and the number of discount offers.
• The second line contains (n) floating-point numbers representing the original prices of products (1) to (n).
• Then, (m) lines follow, each with two integers and a floating-point number: (A) (B) (P), indicating that if product (A) is purchased, you can buy product (B) at the discounted price (P) per unit.
• The next line contains an integer (k), the number of required products.
• The last line contains (k) distinct integers representing the product numbers that you must purchase (each exactly once).

outputFormat

Output the minimum total cost to purchase all the required products. The answer should be printed as a floating-point number with exactly two digits after the decimal point.

sample

3 2
2.50 10.00 1.80
2 1 2.00
1 3 1.50
3
1 2 3

13.50