Optimal One-Day Shopping with Discounts

Little Blue plans to purchase n different items (one of each) with given original prices. Nearby, there are m shops. The i-th shop offers a discount during the days from s_i to t_i (inclusive). On a discount day at that shop, an item with original price b costs \(\lfloor\frac{b \cdot p_i}{100}\rfloor\) dollars; on other days, the item must be bought at the full price.

Being very busy, Little Blue can choose only one day to do all his shopping. On that day, for each item, he can purchase it from any shop. For each item, he will obviously choose the shop which offers the minimum cost (either discounted or full price). It is guaranteed that all items can be purchased.

Your task is to determine the minimum total cost required to buy all n items by optimally choosing the day to shop.

inputFormat

The input is given as follows:

n m
b1 b2 ... bn
s1 t1 p1
s2 t2 p2
...
sm tm pm

Where:

• n is the number of items.
• m is the number of shops.
• The second line contains n integers, where the j-th integer bj is the original price of the j-th item.
• Each of the next m lines contains three integers si, ti, and pi, meaning that the i-th shop offers a discount from day si to day ti (inclusive) with discount rate pi. The discounted price for an item of original price b is \(\lfloor\frac{b \cdot p_i}{100}\rfloor\).

outputFormat

Output a single integer — the minimum total cost to purchase all items on an optimally chosen day.

sample

3 2
100 200 300
1 3 90
2 4 80

480