Description

一场流星雨穿过了沃尔王国，人们推测这是神的惩罚。许多人聚集在法师洪利的门口，向他祈祷，用他的咒语保护他们。热情的洪利很快给了他们祝福。$Hongly$ 的魔法需要使用 $n$ 个魔法塔，它们排成一条直线，编号为 $1、2、3、…、n$。每个塔都需要一些魔法值来施展这个法术。每个塔的初始魔法值为 $0$。$Hongly$ 需要向魔法塔添加一些魔法成分，以增加其魔法值。当一个塔中添加一个单位的魔法成分时，它将在半径 $k$ 内增加附近所有魔法塔的魔法值都会 $+1$，其中 $k$ 称为有效半径。例如，假设第 $i$ 个魔法塔添加了 $1$ 个单位的魔法成分，当 $k=1$ 时，只有魔法塔 $i$ 将其魔法值加 $1$，当 $k=2$ 时，魔法塔 $i− 1、i、i+1$ 将使其魔法值增加 $1$，依此类推。所有塔的有效半径相同。为了保护人民，第i座魔法塔至少需要魔法值的 $p_i$ 点。然而，魔法不是随意使用的，当一个范围内有太多魔法成分时，可能会导致大爆炸。所以在洪利的魔法塔中有 $q$ 条限制。第 $i$ 个限制包含三个整数 $L_i、R_i、B_i$，这意味着在 [$L_i,R_i$] 之间的魔法塔总魔法成分不能大于$B_i$。洪利很高兴帮助村民，但担心爆炸。现在，他想知道是否有一种方法来放置配料，以满足所有魔法塔的魔法值要求，以使用该咒语，同时避免爆炸。如果可以，他还想知道需要使用的魔法成分的最小值。

Input Format

第一行一个整数 $T$（$1 \le T \le 15$）表示有T组测试样例对于每组测试第一行包含两个整数 $n，k$（$1 \le n \le 10^4, 1 \le k \le $）表示魔法塔的数量和魔法塔有效半径。第二行 $n$ 个整数，$p_1,p_2 \cdots p_n$（$1 \le p_i \le 10^3$）表示n个魔法塔所需的魔法成分。第三行一个整数 $q$（$0 \le q \le 10^2$）表示有 $q$ 条限制接下来 $q$ 行，每行三个整数 $L_i,R_i,B_i$（$1 \le L_i \le R_i \le n, 0 \le B_i \le 10^4 $）表示在$L_i$到$R_i$之间魔法成分的和不超过$B_i$。

Output Format

对于每组测试输出一个整数，表示需要使用的魔法成分的最小值。如果不能满足所有要求，输出 $-1$。

3
5 2
2 2 0 10 3
1
1 5 11
5 2
2 2 0 10 3
1
2 3 0
3 2
3 0 6
2
1 1 0
3 3 0

-1
12
6

Source

Online Judge http://127.0.0.1