Problem: light_show (2019 round3)

Melody is visiting the renowned Notre-Dame Basilica church in Montréal,
Canada. Aside from appreciating its beautiful architecture, she's there to see
a spectacular light show scheduled to be held within!

Representing the cross-sectional view of the church as a 2D plane, it has a
mirror-covered ceiling made up of two 45-degree line segments, the first
running from (0, 0) to (**H**, **H**) and the second running from (**H**,
**H**) to (2**H**, 0).

**N** lasers have been set up on the floor, pointing upwards, with the _i_th one at integral coordinates (**Xi**, 0) emitting a coloured beam of either red (if **Ci** = 1) or blue (if **Ci** = 2) light. All **N** lasers are at distinct positions, and there's no laser directly under the center of the ceiling (at x-coordinate **H**). If uninterrupted, each laser's beam travels vertically upwards until it hits a point on the ceiling, at which point it bounces to travel horizontally until it hits another point on the ceiling, at which point it bounces to travel vertically downwards and eventually hits another point on the floor. No laser has been set up such that its beam can possibly end up directly hitting another laser at the end of its path. In other words, if there's a laser at coordinates (x, 0), there's guaranteed to be no laser at coordinates (2**H** \- x, 0). 

For example, if **H** = 5 and there's a single red laser at coordinates (7,
0), the church would look as follows:

![]({{PHOTO_ID:984673281988054}})

Melody thinks it looks pretty when laser beams interact with one another, but
not when red and blue beams clash, so she's going to take matters into her own
hands to optimize the show's appearance. She will use drones to suspend 0 or
more blockers in the air within the church, each occupying a single point
(possibly with non-integral coordinates) strictly above the x-axis and
strictly underneath the ceiling. Each laser beam stops traveling as soon as it
hits a blocker.

Let `I(i, j)` be true if lasers _i_ and _j_ intersect (in other words, if
there exists at least one point which both of their beams pass through). If
two laser beams hit the same blocker, they are not considered to intersect at
that blocker's coordinates. The quality **Q** of a light show, in Melody's
eyes, is the number of unordered pairs of laser beams (_i_, _j_) for which
`I(i, j)` is true and **Ci** = **Cj**. However, if there is any intersecting
pair of differently-coloured laser beams (i.e. there exists some pair of beams
(_i_, _j_) for which `I(i, j)` is true and **Ci** ≠ **Cj**), then the quality
of the light show is instead 0.

### Input

Input begins with an integer **T**, the number of light shows that Melody
watches. For each show, there is first a line containing the space-separated
integers **H** and **N**. Then, **N** lines follow, the _i_th of which
contains the space-separated integers **Xi** and **Ci**.

### Output

For the _i_th show, print a line containing "Case #_i_: " followed by a single
integer **Q**, the maximum possible quality of the light show.

### Constraints

1 ≤ **T** ≤ 150  
2 ≤ **H** ≤ 1,000,000,000  
1 ≤ **N** ≤ 4,000  
1 ≤ **Xi** ≤ 2**H** \- 1  
**Xi** ≠ **H**   
1 ≤ **Ci** ≤ 2  

### Explanation of Sample

In the first case, if no blockers are placed, all three unordered pairs of red
lasers will intersect with one another for a quality of 3:

![]({{PHOTO_ID:945646162539269}})

In the second case, if Melody were to place no blockers, there would be two
same-colour laser beam intersections (one involving the red lasers and another
involving the blue ones), but there would also be at least one different-
colour laser beam intersection, so this is not ideal as the quality is 0:

![]({{PHOTO_ID:282212846231841}})

If she instead places one blocker at coordinates (2.5, 1), blocking the first
laser, and another at (6, 2), blocking both both the second and fourth lasers,
then one same-colour laser beam intersection would be achieved (between the
second and third lasers at coordinates (7, 2)) for a quality of 1:

![]({{PHOTO_ID:711991349348175}})



Sample input:
5
5 3
4 1
9 1
2 1
5 4
1 1
8 2
3 2
6 1
12 6
15 2
22 1
4 2
14 1
23 1
19 2
53 9
7 1
19 1
23 2
40 2
54 2
81 1
85 2
94 1
102 1
8128376 30
259694 2
10267200 2
591548 2
5755696 2
4307513 2
5863522 2
10040589 1
2234412 1
5086932 1
14706276 1
15430629 2
2150128 2
14561793 1
7991506 2
824138 2
3450600 2
6482303 1
11413148 1
12215231 2
7578498 1
13184008 2
6684996 1
11579040 1
2662824 1
13334004 2
5954542 1
7364389 1
8028062 1
11858536 1
15223536 2


Sample output:
Case #1: 3
Case #2: 1
Case #3: 4
Case #4: 10
Case #5: 112



Code: // Light Show
// 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-12;
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);
}

#define LIM 4001

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int H,N;
	int i,j,c,d;
	PR P[LIM];
	static int dyn[LIM][LIM][2];
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(H),Read(N);
				Fox(i,N)
					Read(P[i].x),Read(P[i].y),P[i].y--;
			// sort by position
			sort(P,P+N);
			// DP
			Fill(dyn,-1);
			dyn[0][0][0]=0;
				Fox(i,N)
					Fox(j,i+1)
						Fox(c,2)
							if ((d=dyn[i][j][c])>=0)
								if (P[i].y==c)
									Max(dyn[i+1][j+1][c],d+j); // add on
								else
								{
									Max(dyn[i+1][j][c],d); // skip
									Max(dyn[i+1][1][1-c],d); // switch colour
								}
			// find answer
			int ans=0;
				Fox(j,N+1)
					Fox(c,2)
						Max(ans,dyn[N][j][c]);
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}