카풀 매칭

당신은 친구를 도와 새로운 카풀 앱을 개발해야 한다. 그중 운전자와 승객을 매칭하는 알고리즘을 당신이 개발해야 한다. 현재 이 앱은 베타 버전이기 때문에 동서로 길게 늘어진 고속도로 위에 위치한 지역에서만 서비스를 하고 있으며 아래와 같은 제한이 있다.

• 모든 운전자와 승객은 가장 동쪽에 위치한 "출발지" 도시에서 출발한다.
• 총 N명의 승객이 있으며, i번째 승객은 출발지에서 서쪽으로 xi 미터 떨어진 곳에 위치한 목적지로 가고 싶어한다 (0 < xi).
• 총 M명의 운전자가 있으며, j번째 운전자는 출발지에서 서쪽으로 yj 미터 이상 zj 미터 이하 떨어진 곳으로 가고 싶어하는 승객을 최대 한 명 태워줄 의향이 있다 (0 < yj ≤ zj).

당신은 이 조건들을 만족하면서 최대한 많은 승객-운전자 쌍을 매칭시키는 알고리즘을 작성해야 한다.

예를 들어, 3명의 승객과 3명의 운전자가 있을 때 x, y, z 값이 아래와 같다고 하자.

• x = [10, 20, 30]
• y = [8, 2, 25]
• z = [8, 18, 35]

이 경우 승객 1, 2, 3은 각각 정확히 10미터, 20미터, 30미터 떨어진 곳으로 가고 싶어하며, 운전자 1은 정확히 8미터 떨어진 곳으로 가려는 승객을 태울 의향이 있고, 운전자 2는 2미터 이상 18미터 이하 떨어진 곳으로 가려는 승객을 태울 의향이 있고, 운전자 3은 25미터 이상 35미터 이하 떨어진 곳으로 가려는 승객을 태울 의향이 있다.

이 경우 승객 1과 운전자 2, 승객 3과 운전자 3을 매칭시키면 총 두 쌍을 매칭시킬 수 있고, 이보다 많은 수의 승객-운전자 쌍을 매칭시킬 수 있는 방법은 없다.

입력으로 N, M, 그리고 x, y, z 값들을 입력 받아 최대한 많은 승객-운전자 쌍을 매칭시키면 몇 쌍을 매칭시킬 수 있는지 계산하는 프로그램을 작성하시오.

첫 줄에 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 10).

각 테스트 케이스의 첫 줄에는 N, M이 주어진다.

그 다음 줄에 xi가 공백으로 구분되어 주어진다 (1 ≤ xi ≤ 1,000,000,000).

다음 M줄에 걸쳐 각 줄에 yj와 zj가 공백으로 구분되어 주어진다 (1 ≤ yj ≤ zj ≤ 1,000,000,000).

각 테스트 케이스에 대해, 최대한 많은 승객-운전자 쌍을 매칭시켰을 때 몇 쌍을 매칭시킬 수 있는지 출력한다.