codejam

#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = a; i <= b; i++)
#define FOR(i, n) for (int i = 0; i < n; i++)
#define foreach(it, ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )

#define PI 3.1415926535897932385
#define uint64 unsigned long long
#define Int long long
#define int64 long long
#define all(ar) ar.begin(), ar.end()
#define pb push_back
#define ff first
#define ss second
#define bit(n) (1<<(n))
#define Last(i) ( (i) & (-i) )
#define sq(x) ((x) * (x))
#define mp make_pair
using namespace  std ;

const Int INF   = 1e12 ;
int N , M ;
Int dp[ 721*2 ][ 721*2 ][ 2 ] ;
bool  bin_srch(  vector<pair<int,int> >& arr ,  int pt )
  {
     int lo = 0 ;
     int hi = arr.size() - 1 ;
     int idx = -1 ;
     while( lo <= hi )
       {
          int mid =  ( lo + hi )/ 2 ;
          if( arr[mid].ff <= pt )
              { idx = max(  idx ,mid  ) ; lo = mid + 1 ; }
          else hi = mid - 1 ;

       }

     if(  idx == -1 )return false  ;
     if(  arr[idx].ss > pt )return true ;-
     return false ;

  }

Int rec(  int Aleft , int Bleft , int pt  , int last , vector<pair<int,int> >&A , vector<pair<int,int> >& B )
 {
    if( Aleft < 0 or Bleft < 0 )return INF ;
    if( Aleft == 0 and Bleft == 0 )return 0 ;
    Int ans = INF   ;

    if( dp[ Aleft ][ Bleft ][ last ] != -1 ) return dp[ Aleft ][ Bleft ][ last ]  ;
    if( bin_srch( A , pt ) )
      {
        if( last == 0 )ans = min(  ans , rec( Aleft - 1 , Bleft  , pt + 1 , 0 , A , B   ) )  ;
        if( last == 1 )ans = min(  ans , 1+ rec( Aleft - 1 , Bleft  ,pt + 1 ,  0 , A , B   ) )  ;
        dp[Aleft][Bleft][ last ] = ans ;
        return ans ;
      }

     if( bin_srch( B , pt ) )
      {
        if( last == 0 )ans = min(  ans , 1 + rec( Aleft  , Bleft - 1  , pt + 1 , 1 , A , B   ) )  ;
        if( last == 1 )ans = min(  ans ,  rec( Aleft  , Bleft  - 1 ,pt+1, 1 , A , B   ) )  ;
        dp[Aleft][Bleft][ last ] = ans ;
        return ans ;
      }

    if( last == 0 )
      {
         ans = min (  ans , rec( Aleft - 1 , Bleft ,pt+1, 0 , A , B ) ) ;
         ans = min (  ans , 1 + rec( Aleft  , Bleft - 1  ,pt+1, 1 , A , B ) ) ;
      }

    if( last == 1 )
      {
         ans = min (  ans , 1 + rec( Aleft - 1 , Bleft ,pt+1, 0 , A , B ) ) ;
         ans = min (  ans , rec( Aleft  , Bleft - 1  ,pt+1, 1 , A , B ) ) ;

      }

     dp[Aleft][Bleft][last] = ans ;
     return ans ;

 }
int main()
{

  freopen("aa.in", "r", stdin);
  freopen("aa.out", "w", stdout);

  int t ;
  cin >> t ;
  for( int p = 1 ; p <= t ; p ++ )
   {

        memset( dp , -1 , sizeof(dp));
        cin >> N >> M ;
        vector<pair<int,int> >A( N ) ;
        vector<pair<int,int> >B( M ) ;
        FOR( i , N )
           cin >>A[i].ff>>A[i].ss ;

          FOR( i , M )
            cin >> B[i].ff>>B[i].ss ;

        sort( A.begin()  ,  A.end() ) ;
        sort( B.begin( ) , B.end() )  ;
         cout<<"Case #"<<p<<": ";
        Int ans = min( rec( 720 , 720 , 0 ,0, A , B  ), rec( 720 , 720 ,0, 1 , A , B ) ) ;
        cout<<ans<<endl;


   }


}