问题描述
zxa来到Q镇做义工，镇长希望给住在Q镇中轴线上的$n$户人家实现网络覆盖。这$n$户人家可以看作是中轴线上的质点，从东到西依次编号从$1$到$n$，其中第$i(1\leq i < n)$户人家到第$(i+1)$户人家的距离为$d_i$。
zxa负责了这个项目的方案设计，他获悉运营商给出了两种架设网络的方式。一种是花费$a_i$的费用在第$i(1\leq i\leq n)$户人家安装无线路由器和相关网线使得距离第$i$户人家不超过$r_i$的人家（包括第$i$户人家）都能上网。另一种是花费$b_i$的费用为第$i(1\leq i\leq n)$户人家接通光缆使得该户人家能上网。
zxa很好奇，如果镇上为了防止无线电的辐射过大而至多只能在$k$户人家架设无线路由，那么使得这$n$户人家都能上网的最小花费是多少，你能帮助他吗？
输入描述
第一行有一个正整数$T$，表示有$T$组数据。
对于每组数据：
第一行有两个整数$n$和$k$。
第二行有$(n-1)$个正整数，表示$d_1,d_2,\cdots,d_{n-1}$。
接下来$n$行，第$i(1\leq i\leq n)$行有三个正整数$a_i,r_i$和$b_i$。
每一行相邻数字之间只有一个空格。
$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$
输出描述
对于每组数据，输出一行，包含一个正整数，表示使得这$n$户人家都能上网的最小花费。
输入样例
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
Hint
对于第二组样例，zxa在$3$号人家安装无线路由器，在$1$号、$4$号、$5$号人家接通光缆，这样的总代价是$3+3+2+4=12$。
