Time Limit: 8000/4000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

TopSetter is an organization that creates problems. They’ve prepared N problems with estimated difficulty score in range [ $A_i , B_i$ ]. TopHoster would like to host a contest consisting of M problems.

The $i^{th}$ problem should be of difficulty score $C_i$. The $i^{th}$ problem from TopSetter can be used in the contest if and only if its estimated difficulty score range $[A_i, B_i]$ covers the difficulty score c of its target problem in the contest, i.e. $A_i ≤ c ≤ B_i$ . Hosting a contest with M problems needs tohave M distinct problems which satisfy the required difficulty scores for each problem.

Unfortunately, TopSetter doesn’t provide a service to buy specific problems. You can only request a problem set containing K problems and they will give you K distinct problems from all the N problems, but you don’t know which problems will be given.

As TopSetter is the only problem provider for TopHoster, TopHoster would like to know the least number K of problems they need to buy to make sure they can host a contest.

The $i^{th}$ problem should be of difficulty score $C_i$. The $i^{th}$ problem from TopSetter can be used in the contest if and only if its estimated difficulty score range $[A_i, B_i]$ covers the difficulty score c of its target problem in the contest, i.e. $A_i ≤ c ≤ B_i$ . Hosting a contest with M problems needs tohave M distinct problems which satisfy the required difficulty scores for each problem.

Unfortunately, TopSetter doesn’t provide a service to buy specific problems. You can only request a problem set containing K problems and they will give you K distinct problems from all the N problems, but you don’t know which problems will be given.

As TopSetter is the only problem provider for TopHoster, TopHoster would like to know the least number K of problems they need to buy to make sure they can host a contest.

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with 2 integers, N and M. Then N lines follow, each line consists of 2 integers representing the difficulty score range of the $i^{th}$ problem, $A_i and B_i$ . The last line of each test case consists of M integers representing the target difficulty scores of the M problems $C_i$ .

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the least number of problems which the TopHoster needs to buy.

Output “IMPOSSIBLE!” if it’s impossible.

## limits

$\bullet 1 ≤ T ≤ 100.$

$\bullet 1 ≤ N, M ≤ 10^5.$

$\bullet 1 ≤ A_i ≤ B_i ≤ 10^9.$

$\bullet 1 ≤ C_i ≤ 10^9.$

Output “IMPOSSIBLE!” if it’s impossible.

$\bullet 1 ≤ T ≤ 100.$

$\bullet 1 ≤ N, M ≤ 10^5.$

$\bullet 1 ≤ A_i ≤ B_i ≤ 10^9.$

$\bullet 1 ≤ C_i ≤ 10^9.$

提交代码