一场流星雨经过了沃尔王国，人们纷纷猜测这是神灵的惩罚。许多人聚集在法师 Hongly 的门前，祈求他用咒语保护他们。热心的 Hongly 很快给予了他们祝福。

Hongly 的咒语需要使用 $n$ 座排成一行的魔法塔，编号为 $1, 2, 3, \dots, n$。每座塔都需要一定的魔法值来施展咒语，且每座塔的初始魔法值为 $0$。Hongly 需要向魔法塔添加一些魔法原料以增加其魔法值。当向某座塔添加 $1$ 单位魔法原料时，它会使半径为 $k$ 范围内的所有邻近魔法塔的魔法值增加 $1$，其中 $k$ 被称为有效半径。例如，假设向第 $i$ 座魔法塔添加 $1$ 单位魔法原料，当 $k=1$ 时，只有第 $i$ 座魔法塔的魔法值增加 $1$；当 $k=2$ 时，第 $i-1, i, i+1$ 座魔法塔的魔法值增加 $1$，以此类推。所有塔的有效半径相同。为了保护人民，第 $i$ 座魔法塔需要至少 $p_i$ 点魔法值。

然而，魔法不能随意使用，当某个范围内魔法原料过多时，可能会导致大爆炸。因此，Hongly 的魔法塔之间存在 $q$ 条限制。第 $i$ 条限制包含三个整数 $L_i, R_i, B_i$，这意味着魔法塔 $[L_i, R_i]$ 中的魔法原料总和不能超过 $B_i$。

Hongly 很乐意帮助村民，但又担心爆炸。现在他想知道是否存在一种放置原料的方法，既能满足所有魔法塔的魔法值要求，又能避免爆炸。如果存在，他还想知道所需魔法原料的最小值。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $T(1 \le T \le 15)$。接下来是各测试用例的描述。

每个测试用例的输入数据包含 $q+3$ 行。

第一行包含两个整数：$n(1 \le n \le 10000)$ 和 $k(1 \le k \le \lfloor \frac{n}{2} \rfloor)$，分别代表魔法塔的数量及其有效半径。

第二行包含 $n$ 个整数：$p_1, p_2, p_3, \dots, p_n(1 \le p_i \le 1000)$，其中 $p_i$ 代表第 $i$ 座塔所需的魔法值。

第三行包含一个整数 $q(0 \le q \le 100)$，代表限制的数量。

接下来的 $q$ 行，每行包含 $3$ 个整数：$L_i, R_i, B_i(1 \le L_i \le R_i \le n, 0 \le B_i \le 10000)$，含义如上所述。

输出格式

对于每个测试数据，输出一行，包含一个整数，代表所需的最小魔法原料总量。如果无法满足条件，输出 "-1"（不含引号）。

样例

输入 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

-1
12
6