406384: GYM102394 A Artful Paintings

A. Artful Paintingstime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

Painting is really a romantic activity. Painting on cubes is even more romantic. And creating artful paintings on cubes is the most romantic thing to do.

$$$N$$$ cubes are lined up in a row and they are indexed from $$$1$$$ to $$$N$$$ from left to right. The task for you is to choose some of the cubes and paint them. However, there are some rules that you must not violate, so that the painting will be artful. There are two types of rules, described below:

1. The number of painted cubes whose index belongs to the interval $$$[L_i,R_i]$$$ must not be strictly fewer than $$$K_i \ (1 \le i \le M_1)$$$.
2. The number of painted cubes whose index does not belong to the interval $$$[L_i,R_i]$$$ must not be strictly fewer than $$$K_i \ (1 \le i \le M_2)$$$.

Painting is also a tiring activity, so the number of cubes you paint should be as small as possible.Input

The input contains multiple cases. The first line of the input contains a single integer $$$T\ (1 \le T \le 100)$$$, the number of cases.

For each case, the first line of the input contains three integers $$$N$$$, $$$M_1$$$ and $$$M_2$$$ ($$$1 \le N \le 3\,000$$$, $$$0 \le M_1,M_2 \le 3\,000$$$), denoting the number of cubes, the number of rules of type 1, and the number of rules of type 2. The next $$$M_1$$$ lines each contains three integers $$$L_i,R_i,K_i$$$ $$$(1 \le i \le M_1, 1 \le L_i \le R_i \le N, 0 \leq K_i \leq R_i-L_i+1)$$$, describing a rule of type 1. The next $$$M_2$$$ lines each contains three integers $$$L_i,R_i,K_i$$$ $$$(1 \le i \le M_2, 1 \le L_i \le R_i \le N, 0 \leq K_i \leq N-(R_i-L_i+1))$$$, describing a rule of type 2.

It is guaranteed that the sum of $$$N$$$ over all cases doesn't exceed $$$3\,000$$$, the same is true for the sum of $$$M_1$$$ and the sum of $$$M_2$$$.

Output

For each case, print a single integer in a single line, the smallest number of cubes you need to paint.

ExampleInput

1
3 1 1
1 2 1
2 2 1

Output

1