A:

Sample Input
2
3
1 2 3
5
10 20 30 20 20
Sample Output
Case #1: 5
Case #2: 80


B:

Sample Input
2
1 1 1
1200
34
2 3 2
100 10 1
10 10
Sample Output
Case #1: 1234
Case #2: 12

C:

Sample Input
2
2 2
NY YN
4 2
NN NY YN YY
Sample Output
Case #1: 1
Case #2: 7

D:

Sample Input
2
4 0 3
1 0 0 2
4 1 4
1 0 2 0
1 3
Sample Output
Case #1: 2
Case #2: 2

E:

Sample Input
3
3 1
1 4
2 3
5 6
3
3 2
1 10
3 4
7 9
4 8
3 3
1 2
5 6
8 9
1 5 10
Sample Output
Case #1: 2
Case #2: 2
Case #3: IMPOSSIBLE!

F:

Sample Input
2
3 4
3 1 1 2
1 1 2 1
1 0 5 5
5 4 2 3
2 2 3 2
4 2 6 6
5
2 2 2 2
1 1 3 4
1 4 2 4
1 1 1 2
2 2 3 4
1 2
0 1
2 2
1
1 1 1 2
Sample Output
Case #1:
1
-1
5
13
-1
Case #2:
-1

G:

Sample Input
2
5
0 0 0 1 2
0 0 1 0 2
0 1 1 1 2
1 0 1 1 2
1 0 0 1 5
9
1 1 3 1 1
1 1 1 3 2
3 1 3 3 2
1 3 3 3 1
1 1 2 2 2
2 2 3 3 3
3 1 2 2 1
2 2 1 3 2
4 1 5 1 4
Sample Output
Case #1: 8
Case #2: 4

H:

Sample Input
1
3 4
3 40 77 64
3 10 40 20
3 40 20 77
2 40 77
2 77 64
2 40 10
2 20 77
Sample Output
Case #1: 2

        
  
Hint
For the first test case, there are 3 projects and 4 engineers. One of the optimal solution is to assign the first(40 77) and second engineer(77 64) to project 1, which could cover the necessary areas 40, 77, 64. Assign the third(40 10) and forth(20 77) engineer to project 2, which could cover the necessary areas 10, 40, 20. There are other solutions, but none of them can finish all 3 projects.
So the answer is 2.

I:

Sample Input
2
100 3 2
0 20
1 15 10
1 2 1
1 2 2 1 3 1
2 1 3 2
100 3 2
1 3 1
1 4 1
0 10
3 1 1 3
3 1 2 2
Sample Output
Case #1: 330
Case #2: 121

J:

Sample Input
1
10 IJU
UIV GEV LJTV UKV QLV TZTV AKOV TKUV
GAV DVIL TDBV ILVTU AKV VTUD IJU IEV
HVDBT YKUV ATUV TDOV
TKUV UIV GEV AKV AKOV GAV DOV TZTV
AVDD IEV LJTV CVQU HVDBT AKVU XIV TDVU
OVEU OVBB KMV OFV
QLV OCV TDVU COV EMVU TEV XIV
VFTUD OVBB OFV DVHC ISCTU VTUD OVEU DTV
HEVU TEOV TDV TDBV CKVU
CVBB IJU QLV LDDLQ TZTV GEV GAV KMV
OFV AVGF TXVTU VFTUD IEV OVEU OKV DVIL
TEV XIV TDVU TKUV
UIV DVIL VFTUD GEV ATUV AKV TZTV QLV
TIV OVEU TKUV UKV IEV OKV CVQU COV
OFOV CVBB TDVU IOV
UIV TKUV CVBB AKV TZTV VFTUD UKV GEV
QLV OVEU OVQU AKOV TDBV ATUV LDDLQ AKVU
GAV SVD TDVU UPOHK
Sample Output
Case #1: 4

        
  
Hint
For the first test case, the optimal solution is X = 6 and Y = 4, at this time the advanced schools were [UIV, TKUV, QLV, CVBB, GEV, OCV, AKV, TZTV, VFTUD, UKV].

        
K:

Sample Input
3
3 3
###
#.#
##o
1
0 0 N E
1
0 2 N

3 3
#m.
.xb
o##
2
0 0 N E
0 2 E S
2
1 0 W
2 0 W

4 4
o.bo
obBo
b.b.
Bb..
1
0 1 N E
1
2 3 E
Sample Output
Case #1:
###
#o#
##.
Case #2:
#xb
..o
m##
Case #3:
b.ob
o.Bo
b...
Bbob

L:

Sample Input
4
2016-03-13 01:59:59
2016-03-13 02:00:00
2016-11-06 00:59:59
2016-11-06 01:00:00
Sample Output
Case #1: PST
Case #2: Neither
Case #3: PDT
Case #4: Both