Minimizing Bicycle Ride Expenses with Ride Cards

During a long summer holiday of n days, Xiao Rei plans to ride a shared bicycle each day for s_i minutes, with a cost of c per minute. To save money, she can buy ride cards from the APP. There are m types of ride cards available. The i-th ride card has:

• Price w_i (in yuan),
• Validity period d_i days (starting from the day of purchase),
• Free riding time per day: t_i minutes within the validity period.

Xiao Rei can purchase any ride card any number of times, and can even hold multiple cards whose valid periods overlap. On any day, if several ride cards are active, the free riding time for that day is \( \max\{t_i\} \) (i.e. the maximum among all active cards). For any riding time beyond the available free minutes that day, she must pay c per minute.

Help Xiao Rei to minimize her total expenditure during the holiday by planning the optimal purchase strategy.

The input format is as follows:

n c
s1 s2 ... sn
m
w1 d1 t1
...
wm dm tm

The output is a single integer representing the minimum total cost.

inputFormat

The first line contains two integers n and c — the number of days in the holiday and the cost per minute of riding.

The second line contains n integers s₁, s₂, ..., s_n where s_i represents the riding time (in minutes) on the i-th day.

The third line contains a single integer m — the number of types of ride cards available.

Each of the next m lines contains three integers w_i, d_i, t_i describing a ride card.

outputFormat

Output a single integer which is the minimum total amount Xiao Rei needs to spend for her holiday rides.

sample

3 2
3 4 5
1
5 2 3

16