With the arrival of midsummer, Rei has a vacation lasting $n$ days. To make the most of this time, she plans to ride a shared bike every day to enjoy the fresh outdoor air. According to Rei's plan, she will ride for $s_i$ minutes on day $i$, and the cost per minute of riding is $c$ yuan.
To save money, Rei intends to purchase some riding passes offered by the app. She knows that there are $m$ types of riding passes available. The details for the $i$-th type of pass are as follows:
- Price $w_i$: The cost of each pass is $w_i$ yuan;
- Validity period $d_i$: Valid for $d_i$ consecutive days starting from the day of purchase;
- Free time $t_i$: Within the validity period, the first $t_i$ minutes of riding each day are free.
Rei can purchase any type of riding pass multiple times and can hold multiple valid riding passes at the same time. If multiple riding passes are valid on a certain day, the free riding time available for that day is the maximum of the $t_i$ values among those passes. Any riding time exceeding the free time is still charged at $c$ yuan per minute.
Rei wants to minimize her total riding expenses during the vacation. Please help her calculate the minimum total expenditure for her riding during the vacation.
Input
The input is read from standard input.
The first line contains three integers $n, m, c \; (1\le n\le 150, 1\le m, c\le 10^4)$, representing the number of days in the vacation, the number of types of riding passes, and the cost per minute of riding, respectively.
The second line contains $n$ integers, where the $i$-th integer represents the number of minutes $s_i$ Rei rides on day $i \; (1 \le s_i\le 150)$.
The next $m$ lines each contain three integers $w_i, d_i, t_i \; (1\le w_i\le 10^9, 1\le d_i\le n, 1\le t_i\le 150)$, representing the price, validity period in days, and free riding time of the $i$-th type of pass, respectively.
Output
Output to standard output.
Output a single integer representing the minimum total expenditure for Rei's riding during the vacation.
Examples
Input 1
5 2 2
30 40 50 20 10
10 3 20
15 2 30Output 1
100Note 1
Rei's optimal strategy is: purchase the second type of pass on the first and second days, and purchase the first type of pass on the third day. In this case, the free time for the first three days is $30$ minutes, and the free time for the last two days is $20$ minutes. She needs to pay for an additional $10$ minutes of riding on the second day and $20$ minutes on the third day. The total cost for purchasing the passes is $15+15+10=40$ yuan, and the additional riding cost is $(10 + 20) \times 2 = 60$ yuan, for a total expenditure of $100$ yuan. It can be proven that no scheme with a lower total expenditure exists, so the output is $100$.
Input 2
8 4 1
5 10 9 3 9 8 3 1
11 4 5
12 7 4
10 2 9
5 3 4Output 2
33