Lò Phản Ứng Hạt Nhân

Bessie thiết kế lò phản ứng hạt nhân với $N$ thanh nhiên liệu. Mỗi thanh $i$ có khoảng hoạt động ổn định $[l_i,r_i]$ và mức năng lượng $a_i$ (số nguyên). Thanh $i$ tạo ra điện nếu $l_i\le a_i\le r_i$.

Có $M$ ràng buộc, mỗi ràng buộc yêu cầu $a_x+a_y=z$. Giá trị $a_i$ có thể là bất kỳ số nguyên nào (không giới hạn).

Tìm số thanh nhiên liệu tạo ra điện nhiều nhất, hoặc in $-1$ nếu không tồn tại phép gán hợp lệ.

Dữ liệu vào

• Dòng 1: Số nguyên $T$ (số test case)
• Mỗi test case:
  • Dòng 1: Hai số nguyên $N$ và $M$
  • Dòng 2: $N$ số nguyên $l_1,l_2,\dots ,l_N$
  • Dòng 3: $N$ số nguyên $r_1,r_2,\dots ,r_N$
  • $M$ dòng tiếp theo: Ba số nguyên $x$, $y$, $z$ (ràng buộc $a_x+a_y=z$)

Dữ liệu ra

Với mỗi test case, in ra số thanh tạo điện nhiều nhất hoặc $-1$.

Ràng buộc

• $1\le T\le 10$
• $1\le N\le 2\times {10}^5$
• Tổng $N$ qua tất cả test case $\le 4\times {10}^5$
• Tổng $M$ qua tất cả test case $\le 4\times {10}^5$
• $1\le x,y\le N$
• $-{10}^9\le l_i\le r_i\le {10}^9$
• $-{10}^9\le z\le {10}^9$

Ví dụ