Minimum Hoses to Cover Fields

You are given T test cases. In each test case, you are given a set of fields, each represented by an interval [s, e] and a list of available hose lengths. A field defined by the interval [s, e] requires a hose of length at least \(e - s + 1\) in order to be fully covered. You can use the same hose for different fields, as long as the hose can individually cover the field's length requirement. For each test case, determine the minimum number of hoses needed to cover all fields if it is possible. If any field cannot be covered by any available hose, output \(-1\) for that test case.

Note: For each field, if there exists at least one hose that has a length greater than or equal to its required length \(\ell = e - s + 1\), then that field is considered covered. The answer for a test case is the total number of fields if every field is covered, otherwise \(-1\).

inputFormat

The first line contains an integer \(T\) representing the number of test cases. The description of each test case follows:

• The first line of each test case contains an integer \(N\), the number of fields.
• Then \(N\) lines follow, each containing two space-separated integers \(s\) and \(e\) denoting the start and end of a field.
• The next line contains an integer \(M\), the number of available hoses.
• The following line contains \(M\) space-separated integers representing the lengths of the available hoses.

outputFormat

For each test case, output a single line containing the minimum number of hoses needed to cover all fields. If it is not possible to cover all fields, output \(-1\).

## sample

4
2
1 4
5 8
3
2 3 4
1
1 5
2
1 2
1
1 4
1
4
4
1 4
5 8
9 12
13 16
1
4

2
-1
1
4

</p>