zxa and wifi

zxa went to Q town as a volunteer, and the town mayor intended to achieve network coverage for the $n$ families living in the town. This $n$ families are able to be seen as the points in the axis, and the families from east to west are numbered from $1$ to $n$, where the distance between the $i$-th family and the $(i+1)$-th family is $d_i(1\leq i < n)$.

zxa was in charge of the planning of this project, and he was informed that the carriers were given two ways to set up the network. One way is using one wireless router and cables associated at the $i$-th family for some families network coverage, where the distance from the $i$-th family to each covered family (include the $i$-th family) is no more than $r_i$ , which needs $a_i$ costs. Another way is using one optical fiber cable at the $i$-th family for the $i$-th family network coverage, which needs $b_i$ costs.

zxa is interested to know, assuming that it is only permitted to use at most $k$ wireless routers for network coverage in order to avoid too large Wi-Fi radiation, then what is the minimum cost for this $n$ families network coverage, can you help him?

The first line contains an positive integer $T$, represents there are $T$ test cases.

For each test case:

The first line contains two positive integers $n$ and $k$.

The second line contains $(n-1)$ positive integers, represent $d_1,d_2,\cdots,d_{n-1}$.

The next $n$ lines, the $i$-th line contains three positive integers $a_i,r_i$ and $b_i$.

There is a blank between each integer with no other extra space in one line.

$1\leq T\leq 100,2\leq n\leq 2\cdot10^4,1\leq k\leq\min(n, 100),1\leq a_i,b_i,d_i,r_i\leq 10^5,1\leq\sum{n}\leq10^5$

For each test case, output in one line a positive integer, repersents the minimum cost for this $n$ families network coverage.

2
2 1
1
12 11 3
1 7 4
5 5
7 4 8 6
13 6 3
14 2 3
3 6 4
11 12 2
9 14 4

1
12

For the second sample, zxa used one wireless router at the $3$-th family and three optical fiber cables at the $1$-th family, the $4$-th family and the $5$-th family, so that the total cost is $3+3+2+4=12$.

BestCoder Round #83