Problem: boomerang_crews (2016 finals)

It's time to settle things once and for all. Your boomerang crew has decided
to challenge their rivals to a boomerang crew battle!

Your crew has **N** members with strengths **A1..N**, while the opposing crew
has **M** members with strengths **B1..M**. The crew battle will proceed as
follows:

  1. Each crew will arrange its members in a line, in some order. 
  2. A throwing contest will take place between the first person in your line, and the first person in your opponents' line. 
  3. Whoever loses the contest (see below for details) will leave their line permanently, while the winner will stay at the front of their line. 
  4. If one of the lines has become empty, that crew loses and the crew battle concludes. 
  5. Otherwise, back to step 2. 

However, you're not about to play fair with your enemies — you've got the
following 3 things going for you:

  1. You will decide the initial ordering of members for _both_ crews (in step 1 of the crew battle). 
  2. When a member of your crew with strength **S** competes in a throwing contest, they'll throw their boomerang a distance of **S** feet. On the other hand, due to a bit of subtle poisoning you've done in advance, your enemies will get tired after each throw. In particular, when a member of the rival crew with strength **S** competes in a throwing contest, such that they've already competed in (and won) **C** throwing contests previously, they'll throw their boomerang a distance of max{**S** \- **C*****D**, 1} feet (where **D** is a set constant). 
  3. In each throwing contest, your crew's member will win if their throw distance is greater than _or equal_ to their opponent's. 

Despite these advantages, it's possible that you'll still be unable to emerge
victorious. However, whether or not you do, you'd like to maximize the number
of throwing contests that members of your crew win over the course of the crew
battle (given that you choose optimal initial orderings for both lines).

### Input

Input begins with an integer **T**, the number of battles. For each battle,
there are three lines. The first line contains the space-separated integers
**N**, **M**, and **D**. The second line contains the **N** space-separated
integers **A1** to **AN**. The third line contains the **M** space-separated
integers **B1** to **BM**.

### Output

For the **i**th battle, print a line containing "Case #**i**: " followed by
the maximum number of throwing contests that your crew can win.

### Constraints

1 ≤ **T** ≤ 75  
1 ≤ **N**, **M** ≤ 100,000  
1 ≤ **Ai**, **Bi**, **D** ≤ 1,000,000,000  

### Explanation of Sample

In the first battle, your single member cannot beat theirs. In the second
battle, they can (just barely). In the fourth battle, one solution is to
arrange their crew as [35, 25, 5] and your crew as [10, 20, 30] to emerge
victorious (in which case, 5 throwing contests will occur, of which your crew
will win the last three).



Sample input:
5
1 1 1
15
16
1 1 1
15
15
1 5 1
10
3 100 4 1 9
3 3 3
30 10 20
5 35 25
5 2 10
32 29 1 1 1
48 41


Sample output:
Case #1: 0
Case #2: 1
Case #3: 4
Case #4: 3
Case #5: 2



Code: // BOOMERANG CREWS
// Official Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-9;
const LD PI = acos(-1.0);

//#if DEBUG
#define GETCHAR getchar
/*#else
#define GETCHAR getchar_unlocked
#endif*/

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	int T,t;
	int N,M,D;
	int i,j,c,free;
	int r1,r2,m;
	static int A[100000],B[100000];
	set<PR> S;
	set<PR>::iterator I;
	Read(T);
		Fox1(t,T)
		{
			Read(N),Read(M),Read(D);
				Fox(i,N)
					Read(A[i]);
				Fox(i,M)
					Read(B[i]);
			sort(A,A+N);
			reverse(A,A+N);
			j=free=0;
				Fox(i,M)
					if (B[i]<=A[0])
						free++;
					else
						B[j++]=B[i];
			M=j;
			sort(B,B+M);
			r1=0,r2=min(N,M);
				while (r2>r1)
				{
					m=(r1+r2+1)>>1;
					S.clear();
						Fox(i,m)
							S.insert(mp(A[i]%D,i));
					c=1;
						Fox(i,m)
						{
							I=S.lower_bound(mp(B[i]%D,-1));
								if (I==S.end())
									I=S.begin();
							j=A[I->y],S.erase(I);
							c+=(B[i]-j+D-1)/D-1;
								if (c>N-m)
									goto Bad;
						}
					r1=m;
					continue;
Bad:;
					r2=m-1;
				}
			printf("Case #%d: %d\n",t,free+r1);
		}
	return(0);
}