Optimal Communication Base Station Placement

There are $N$ villages arranged on a straight line. The position of the first village is $0$, and for every $i>1$, the distance from the first village to the $i$-th village is given by $D_i$. You are allowed to build at most $K$ communication base stations. Building a base station at the $i$-th village costs $C_i$. A village $i$ is considered to be covered if there exists a base station built in some village $j$ such that $$|\text{pos}_i-\text{pos}_j|\le S_i.$$ If village $i$ is not covered, a compensation cost of $W_i$ must be paid. The goal is to choose locations for the base stations (a set of villages of size at most $K$) so that the total cost (the sum of building costs and any necessary compensations) is minimized.

inputFormat

The first line contains two integers $N$ and $K$, where $N$ is the number of villages and $K$ is the maximum number of base stations that can be built.

The second line contains $N-1$ integers: $D_2, D_3, \dots, D_N$, where $D_i$ is the distance from the first village (position $0$) to the $i$-th village.

The following $N$ lines each contain three integers $C_i$, $S_i$, and $W_i$, which denote the cost to build a base station at village $i$, the coverage distance for village $i$, and the compensation cost if village $i$ is not covered, respectively.

outputFormat

Output a single integer representing the minimum total cost.

sample

3 1
10 20
100 5 50
150 15 30
200 10 40

120