문제

가은이는 우진이의 새로운 AI 데이터 센터 사업을 위해 원자력 발전소를 설계하고 있다.

발전소 코어는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 연료봉으로 구성된다. ($1 \le N \le 2 \cdot 10^5$) 각 연료봉 $i$는 '안정적인 작동 범위' $[l_i, r_i]$를 가진다. ($-10^9 \le l_i \le r_i \le 10^9$) 이는 가은이가 선택한 해당 연료봉의 에너지 $a_i$가 $l_i \le a_i \le r_i$를 만족할 때만 전력을 생산할 수 있음을 의미한다. 조건을 만족하지 않는 연료봉은 유휴 상태가 되어 전력을 생산하지 않는다. 또한, $a_i$는 항상 정수여야 하며, $a_i$의 값 자체는 $[-10^9, 10^9]$ 범위를 벗어나도 상관없다.

하지만 연료봉 사이의 양자 상호작용으로 인해, 발전소의 붕괴를 막으려면 $M$개의 제약 조건을 만족해야 한다. 각 제약 조건은 $(x, y, z)$ 형태이며, 이는 가은이가 $a_x + a_y = z$를 만족해야 함을 의미한다. ($1 \le x, y \le N$; $-10^9 \le z \le 10^9$)

발전소가 붕괴하지 않도록 하면서 전력을 생산하는 연료봉의 개수를 최대화했을 때, 그 최댓값을 구하시오.

입력

첫째 줄에 독립적인 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10$)

각 테스트 케이스는 다음과 같은 형식으로 주어진다:

첫째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. 둘째 줄에는 $N$개의 정수 $l_1, \dots, l_N$이 공백으로 구분되어 주어진다. 셋째 줄에는 $N$개의 정수 $r_1, \dots, r_N$이 공백으로 구분되어 주어진다. 이어서 $M$개의 줄에 각 제약 조건을 나타내는 세 정수 $x, y, z$가 공백으로 구분되어 주어진다.

모든 테스트 케이스에 대해 $N$의 합과 $M$의 합은 각각 $4 \cdot 10^5$을 초과하지 않는다.

출력

모든 제약 조건을 만족하는 연료봉 에너지의 선택지가 존재하지 않는다면 -1을 출력한다. 그렇지 않다면, 가은이가 달성할 수 있는 전력 생산 연료봉의 최대 개수를 출력한다.

예제 입력 1

2
3 3
1 2 3
1 2 3
1 1 2
2 2 10
1 1 4
3 2
1 2 3
1 2 3
1 1 2
2 2 10

예제 출력 1

-1
2

예제 입력 2

1
3 2
10 -10 10
10 -10 10
1 2 0
2 3 0

예제 출력 2

3

예제 입력 3

5
3 3
1 -1 0
2 1 2
1 2 1
1 3 4
2 3 3
1 1
-100
100
1 1 3
1 1
-100
100
1 1 2
1 2
-100
100
1 1 2
1 1 4
1 2
-100
100
1 1 2
1 1 2

예제 출력 3

2
-1
1
-1
1

점수

• 테스트 케이스 4: 모든 제약 조건에 대해 $x = y$이다.
• 테스트 케이스 5-7: 모든 제약 조건에 대해 $|x - y| = 1$이다.
• 테스트 케이스 8-10: 모든 제약 조건에 대해 $|x - y| \le 1$이다.
• 테스트 케이스 11-13: 추가적인 제약 조건이 없다.