Magic

A meteor shower passed through the kingdom of Woll, which led the people to speculate that it was a punishment from the gods. Many gathered at the door of the mage Hongly and prayed to him to protect them with his spells. The enthusiastic Hongly quickly granted them their blessing.

Hongly's spell requires the use of $n$ magic towers lined up in a straight line, numbered as $1, 2, 3, ..., n$. Each tower requires some magic value to cast this spell. And each tower has an initial magic value of $0$ . Hongly needs to add some magic ingredients to the magic tower in order to increase its magic values. When $1$ unit of magic ingredients is added to a tower, it will increase the magic value of all nearby magic towers by $1$ within a radius of $k$, in which $k$ is called effective radius. For example, assuming the $i$-th magic tower is added with $1$ unit of magic ingredients, when $k=1$, only magic tower $i$ will add its magic value by $1$, when $k=2$, magic tower $i-1, i, i+1$ will increase their magic values by $1$, and so on. The effective radius for all towers is the same. For this spell to protect the people, the $i$-th magic tower needs at least $p_{i}$ points of magic value.

However, magic is not free to be used at will, and when there are too many magic ingredients in a range, it can lead to a big explosion. So there are $q$ restrictions among Hongly's magic towers. The $i$-th restriction contains three integers $L_{i},R_{i},B_{i}$, which means that the sum of the magic ingredients in the magic towers $[L_{i},R_{i}]$ cannot be greater than $B_{i}$.

Hongly is glad to help the villagers but is worried about the explosion. Now he wants to know if there is a way to place the ingredients that will meet the magic value requirements of all magic towers for using the spell while avoiding an explosion. If so, he would also like to know the minimum value of magic ingredients that need to be used.

Each test contains multiple test cases. The first line contains the number of test cases $T(1 \le T \le 15)$. Description of the test cases follows.

The input data of each test case has $q+3$ lines.

The first line contains two integers: $n(1\leq n\leq 10000), k(1\leq k \leq \left \lceil \frac{n}{2} \right \rceil)$, representing the number of magic towers and their effective radius.

The second line contains $n$ integers: $p_{1}, p_{2}, p_{3}, ... p_{n}(1\leq p_{i}\leq 1000)$ , where $p_{i}$ represents the magic value required for the $i$-th tower.

The third line contains an integer $q(0\leq q\leq 100)$, representing the number of restrictions.

Next $q$ lines, each line contains $3$ integers:$L_{i},R_{i},B_{i}(1\leq L_{i}\leq R_{i} \leq n, 0\leq B_{i}\leq 10000)$, have the same meaning as described above.

For each test data, output one line contains an integer, representing the minimum amount of magic ingredients required. If the condition cannot be reached, output "$-1$" (without quotes).

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

2022“杭电杯”中国大学生算法设计超级联赛（4）