        CONTEST #3

Run time limit on all problems this week is two seconds per
dataset unless otherwise specified.


Special Competition Rules

At 9:45 sharp, begin a 15 minute ``thinking break'' during which
time you do not use the computer (or keyboard) at all.  At
10:00, recommence computing on the keyboard if you wish.


       ffence "Flexible Fence" "Brian Dean"

FJ has N cows at distinct (x,y) positions in his almost infinitely
large 2D planar field.  He has recently purchased a flexible
rectangular fence with total area A (1 <= A <= 2,000,000).  Due to
zoning regulations, FJ must position the fence such that its sides
are aligned with the x and y axes.  When positioned, all four sides
of the fence must have integer lengths.
FJ's herd of N cows (1 <= N <= 1,000) is grazing in a field;
they are approximated as points. FJ wishes to position the fence
such that it encloses the most cows. A cow is enclosed if it is
within or touching the fence.  What is the greatest number of cows
FJ can enclose?
Input Format
 Line 1: Two integers: A and N
 Lines 2..N+1: Each line contains a pair of integers representing
the X,Y coordinates of a cow (all coordinates are representable as
32-bit signed integers)
Sample Input
9 4
0 0
0 1
1 0
1 1

Output Format
A line with a single integer that is the largest number of cows that
can be enclosed by the fence.

Sample Output
4



         gates "Those Darn Gates" "Brian Dean"


FJ's fenced-in field has on one of its sides a row of N (1 <= N <=
10,000) electronically-controlled gates numbered 1..N.  FJ's control
room has K (1 <= K <= 100) switches, each of which opens some specified
contiguous block of gates (blocks which are by no means promised to be
mutually exclusive).
Each switch additionally has a power utilization cost associated
with it.  Calculate for FJ the minimum cost to open all N gates.

Input Format
Line 1: Two integers: N and K
Lines 2..K+1: Three integers: C (signed 32-bit), which
specifies the cost, followed N0 and N1 (N0 <= N1), which specify
the contiguous set of gates opened by the switch

Sample Input
5 3
5 1 4
5 2 5
2 3 5

Output Format
A single line with a single integer that is the minimum cost to open
all N gates. The minimum cost is guaranteed to fit in a signed 32-bit
integer. Output the integer -1 if it is not possible to open all N
gates.

Sample Output
7


         "lsched" "Lifecow Scheduling" "Russ Cox"

The cows are going to the beach where lifecows will watch the other
cows swim and sunbathe. The cows need your help in creating their
lifecow schedule.
Given N (1 <= N <= 35) stations, S (1 <= S <= 10) shifts, and
schedules for C (1 <= C <= 90) cows (shifts when each cow can work),
show a lifecow schedule such that each cow works no more than one
shift and each station always has two lifecows.
Input Format
Line 1: Three integers, N, S, and C
Lines 2..C+1: Each line contains S integers, each 0 or 1, where 1
denotes a cow's availability for a given shift. The first line
represents the schedule for cow 1; the second line represents the
schedule for cow 2; etc.

Sample Input
2 2 10
1 1
1 1
1 0
1 0
0 1
1 1
0 1
1 1
0 0
0 1

Output Format
A scheduling matrix of S lines, each representing a shift and the
cows that work on it. Each line has 2*N integers telling which
cows are working a given shift (output two cows for the first shift
first, etc.); order of cows within a shift is unimportant.
If no schedule is possible, output a single line with a single 0.

Sample Output
1 2 3 4
5 6 7 8
[Other answers are possible]
