Bessie đang thiết kế một lò phản ứng hạt nhân để cung cấp năng lượng cho CowWeave, hoạt động kinh doanh trung tâm dữ liệu AI mới đầy lợi nhuận của Nông dân John!

Lõi lò phản ứng gồm \(N\) (\(1\le N\le 2\cdot 10^5\)) thanh nhiên liệu, được đánh số từ \(1\) đến \(N\). Thanh thứ \(i\) có một “phạm vi vận hành ổn định” \([l_i,r_i]\) (\(-10^9\leq l_i\leq r_i\leq 10^9\)), nghĩa là nó chỉ có thể phát điện nếu năng lượng \(a_i\) (do Bessie chọn) thỏa mãn \(l_i\le a_i\le r_i\); nếu không, nó ở trạng thái không hoạt động và không phát điện. Ngoài ra, \(a_i\) luôn phải là một số nguyên. Lưu ý rằng \(a_i\) có thể là bất kỳ số nguyên nào, không bị giới hạn trong \([-10^9,10^9]\).

Tuy nhiên, các tương tác lượng tử giữa những thanh nhiên liệu tạo ra \(M\) ràng buộc có dạng \((x,y,z)\), trong đó Bessie phải thỏa mãn \(a_x+a_y=z\) (\(1\leq x,y\leq N\) và \(-10^9\le z\le 10^9\)) để ngăn lò phản ứng bị nóng chảy.

Hãy giúp Bessie tìm số thanh phát điện tối đa mà cô có thể đạt được trong thiết kế của mình mà không làm lò phản ứng bị nóng chảy!

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 10\)), số lượng bộ test độc lập. Mỗi bộ test có định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).
• Dòng thứ hai chứa \(N\) số nguyên \(l_1,\dots,l_N\).
• Dòng thứ ba chứa \(N\) số nguyên \(r_1,\dots,r_N\).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(x\), \(y\) và \(z\), biểu diễn một ràng buộc.

Đảm bảo rằng cả tổng \(N\) lẫn tổng \(M\) trên tất cả các bộ test đều không vượt quá \(4\cdot 10^5\).

Dữ liệu ra

Nếu không tồn tại cách chọn năng lượng cho các thanh sao cho thỏa mãn mọi ràng buộc, hãy in \(-1\). Nếu có, hãy in số thanh phát điện tối đa mà Bessie có thể đạt được.

Ví dụ

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
2

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

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

2
-1
1
-1
1

Phân nhóm

• Input 4: \(x=y\) với mọi ràng buộc.
• Inputs 5–7: \(|x-y|=1\) với mọi ràng buộc.
• Inputs 8–10: \(|x-y|\le 1\) với mọi ràng buộc.
• Inputs 11–13: Không có điều kiện bổ sung.

Nguồn

USACO 2026 First Contest, Silver — bài gốc tiếng Anh “Mooclear Reactor”, tác giả Akshaj Arora: https://usaco.org/index.php?page=viewproblem2&cpid=1543