Maximize Satisfied Farm Requests

You are given several test cases. In each test case, there are n farm requests and a timeline divided into m hours. Each request is represented by a time interval [s, e) (i.e. starting at hour s and ending just before hour e). The farm has a capacity for each of the m hours given in an array. A request can be satisfied if and only if for each hour in its interval, the number of previously satisfied requests in that hour is less than the capacity of that hour.

Your task is to determine the maximum number of requests that can be satisfied for each test case by scheduling the requests greedily (i.e., by processing them in order of their finish times).

Note: For a request with interval \( [s,e) \), it uses up one unit of capacity in every hour from \( s \) (inclusive) to \( e \) (exclusive).

inputFormat

The input is read from standard input and has the following format:

T
n1 m1
s1 e1
s2 e2
... (n1 lines of start and end times)
cap1 cap2 ... capm1
n2 m2
... (similar format for test case 2)
...

Where:

• T is the number of test cases.
• For each test case, the first line contains two integers: n (the number of requests) and m (the number of hours).
• The next n lines each contain two integers representing the start and end time (s and e) of a request.
• The next line contains m integers representing the capacity for each hour from 0 to m-1.

outputFormat

For each test case, output the maximum number of requests that can be satisfied. Each result should be printed on a new line to standard output.

## sample

3
5 6
0 2
1 3
2 5
4 6
3 5
3 2 1 2 3 2
3 5
0 2
1 3
2 4
3 3 3 3 3
3 5
0 2
1 3
2 4
3 2 1 1 1

4
3
2

</p>