Carpool Matching

You must help your friend develop a new carpool app. Part of this work is an algorithm that matches drivers with passengers. Because the app is in beta, it serves only regions along a long highway that runs east to west, with the following restrictions.

• Every driver and passenger departs from the "origin" city, which lies at the easternmost point.
• There are N passengers, and the i-th passenger wants to reach a destination located xi meters west of the origin (0 < xi).
• There are M drivers, and the j-th driver is willing to take at most one passenger who wants to go to a destination between yj and zj meters west of the origin, inclusive (0 < yj ≤ zj).

You must write an algorithm that matches as many passenger-driver pairs as possible while satisfying these conditions.

For example, suppose there are 3 passengers and 3 drivers with the following x, y, and z values.

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

Here passengers 1, 2, and 3 want to go exactly 10, 20, and 30 meters away, respectively. Driver 1 is willing to take a passenger heading exactly 8 meters away, driver 2 is willing to take a passenger heading between 2 and 18 meters away, inclusive, and driver 3 is willing to take a passenger heading between 25 and 35 meters away, inclusive.

In this case, matching passenger 1 with driver 2 and passenger 3 with driver 3 yields two pairs, and no method can match more passenger-driver pairs.

Write a program that reads N, M, and the x, y, and z values from the input and computes the maximum number of passenger-driver pairs that can be matched.

The first line gives the number of test cases T (1 ≤ T ≤ 10).

The first line of each test case gives N and M.

The next line gives the xi values separated by spaces (1 ≤ xi ≤ 1,000,000,000).

The following M lines each give yj and zj separated by a space (1 ≤ yj ≤ zj ≤ 1,000,000,000).

For each test case, print the maximum number of passenger-driver pairs that can be matched.