Problem: connect_the_dots (2019 round1)

There are **N** dots on a 2D grid, the _i_th of which is a point at
coordinates (**Xi**, **Yi**). All coordinates are positive integers, and all
**N** dots' positions are distinct.

You'd like to draw **N** line segments, each of which is either horizontal or
vertical, to "connect" each of the dots to one of the grid's axes. In
particular, for each dot _i_, you'll draw either a horizontal line segment
connecting it to the y-axis (with endpoints (0, **Yi**) and (**Xi**, **Yi**)),
or a vertical line segment connecting it to the x-axis (with endpoints
(**Xi**, 0) and (**Xi**, **Yi**)). Each line segment only counts as
"connecting" the single dot located at its endpoint, even if it happens to
pass through other dots along the way.

No horizontal line segment is allowed to intersect with any vertical line
segment. Line segments are **not** considered to intersect at either of their
endpoints — for example, it's permitted for a horizontal line segment to pass
through the endpoint of a vertical one, or vice versa. Horizontal line
segments are allowed to overlap with other horizontal ones, as are vertical
line segments with other vertical ones.

The cost of drawing a non-empty set of horizontal line segments is equal to
the length of the longest one (in dollars), while the cost of drawing no
horizontal line segments is $0. The cost of drawing a set of vertical line
segments is similarly equal to the length of the longest one (if any), and the
total cost of drawing all **N** line segments is equal to the cost of drawing
the set of horizontal ones plus the cost of drawing the set of vertical ones.

You can choose to draw at most **H** horizontal line segments, and at most
**V** vertical ones. What's the minimum total cost required to connect all
**N** dots to the grid's axes, without using too many of either type of line
segment or causing any horizontal line segments to intersect with vertical
ones, if that can be done at all?

In order to reduce the size of the input, the dots' coordinates will not all
be provided explicitly. Instead, you'll be given **X1**, **X2**, **Y1**,
**Y2**, as well as 8 constants **Ax**, **Bx**, **Cx**, **Dx**, **Ay**, **By**,
**Cy**, and **Dy**, and you must then compute **X3..N** and **Y3..N** as
follows (bearing in mind that intermediate values may not fit within 32-bit
integers):

**Xi** = ((**Ax** * **Xi-2** \+ **Bx** * **Xi-1** \+ **Cx**) modulo **Dx**) + 1, for _i_ = 3..**N**

**Yi** = ((**Ay** * **Yi-2** \+ **By** * **Yi-1** \+ **Cy**) modulo **Dy**) + 1, for _i_ = 3..**N**

### Input

Input begins with an integer **T**, the number of grids. For each room, there
are three lines. The first line contains the space-separated integers **N**,
**H**, and **V**. The second line contains the space-separated integers
**X1**, **X2**, **Ax**, **Bx**, **Cx**, and **Dx**. The third line contains
the space-separated integers **Y1**, **Y2**, **Ay**, **By**, **Cy**, and
**Dy**.

### Output

For the _i_th grid, print a line containing "Case #_i_: " followed by the
minimum total cost (in dollars) required to validly connect all **N** dots to
the grid's axes, or -1 if it's impossible to do so.

### Constraints

1 ≤ **T** ≤ 160  
2 ≤ **N** ≤ 800,000  
0 ≤ **H**, **V** ≤ **N**  
0 ≤ **Ax**, **Bx**, **Cx** **Ay**, **By**, **Cy** ≤ 1,000,000,000  
1 ≤ **Dx**, **Dy** ≤ 1,000,000,000  
1 ≤ **Xi** ≤ **Dx**  
1 ≤ **Yi** ≤ **Dy**  

In the first case, the dots are at coordinates (6, 2) and (3, 4). The cheapest
option is to connect both dots using vertical line segments, having lengths 2
and 4 and altogether costing $4 to draw. The lack of horizontal line segments
costs an additional $0, bringing the total to $4 + $0 = $4.

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

The second case is the same as the first, except that at most one vertical
line may be drawn. The cheapest valid option is now to connect the second dot
using a horizontal line segment (of length 3) while still connecting the first
dot using a vertical one (of length 2). These two line segments do not
intersect, and cost a total of $3 + $2 = $5 to draw.

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

In the third case, not all of the dots can be connected.

In the fourth case, the dots are at coordinates (1, 1), (1, 2), (2, 1), and
(2, 2). You can connect the first dot using a horizontal line segment (of
length 1), and the other dots with vertical ones (of lengths at most 2), for a
total cost of $1 + $2 = $3. Note that this causes two vertical line segments
to overlap (the ones connecting the third and fourth points).

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

In the fifth case, the dots are at coordinates (15, 34), (19, 3), (2, 38),
(13, 17), (18, 14), (25, 15), (42, 18), (9, 11), (26, 34), and (41, 19).



Sample input:
6
2 2 2
6 3 0 0 0 10
2 4 0 0 0 10
2 2 1
6 3 0 0 0 10
2 4 0 0 0 10
2 0 1
6 3 0 0 0 10
2 4 0 0 0 10
4 1 3
1 1 1 0 0 2
1 2 1 0 1 2
10 7 5
15 19 34 41 32 44
34 3 25 2 17 38
10000 6011 4543
434894347 263348046 2565 3970 1267 622277910
524251054 294718567 0 1 3718 689139248


Sample output:
Case #1: 4
Case #2: 5
Case #3: -1
Case #4: 3
Case #5: 45
Case #6: 766791757



Code: // Connect the Dots
// 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 800001

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int N,H,V;
	int i,j,si,a,b,c,d;
	static int G[2][LIM];
	static PR P[LIM];
	static int maxY[LIM];
	set<PR> S;
	set<PR>::iterator I;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input, and generate coordinates
			Read(N),Read(H),Read(V);
				Fox(i,2)
				{
					Read(G[i][0]),Read(G[i][1]),Read(a),Read(b),Read(c),Read(d);
						FoxI(j,2,N-1)
							G[i][j]=((LL)a*G[i][j-2] + (LL)b*G[i][j-1] + c)%d+1;
				}
			// impossible?
			int ans=-1;
				if (H+V<N)
					goto Done;
			// sort dots by X
				Fox(i,N)
					P[i]=mp(G[0][i],G[1][i]);
			sort(P,P+N);
			// precompute Y values' suffix maxes
			maxY[N]=0;
				FoxR(i,N)
					maxY[i]=max(maxY[i+1],P[i].y);
			// consider each possible max horiz. segment length
			ans=2*INF;
			S.clear();
			S.insert(mp(0,-1));
			I=S.begin(),si=0;
				Fox(i,N+1)
				{
					// update set of dots so far
						if (i)
						{
							S.insert(mp(P[i-1].y,i));
								if (mp(P[i-1].y,i)<*I)
									si++;
						}
					// last f dots must use vert. segments
					int f=N-i;
						if (f>V)
							continue;
					// g of the dots so far must also use vert. segments
					int g=max(0,min(N-H,V)-f);
						while (si>g)
							I--,si--;
						while (si<g)
							I++,si++;
					Min(ans,(i?P[i-1].x:0)+max(I->x,maxY[i]));
				}
			// output
Done:;
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}