AMR12G - The Glittering Caves of Aglarond

no tags 

'Strange are the ways of Men, Legolas! Here they have one of the marvels of the Northern World, and what do they say of it? Caves, they say! Caves! Holes to fly to in time of war, to store fodder in! My good Legolas, do you know that the caverns of Helm's Deep are vast and beautiful? There would be an endless pilgrimage of Dwarves, merely to gaze at them, if such things were known to be. Aye indeed, they would pay pure gold for a brief glance!

'And, Legolas, when the torches are kindled and men walk on the sandy floors under the echoing domes, ah! then, Legolas, gems and crystals and veins of precious ore glint in the polished walls; and the light glows through folded marbles, shell-like, translucent as the living hands of Queen Galadriel.' - Gimli, describing to Legolas the Glittering Caves of Aglarond.

While these caves are by and large natural, there is one place where the Men of Rohan have chiselled into the rock to create a magnificent exhibit. You have a wall of the cave consisting of 'lighted diamonds' arranged in a N by M grid (basically, you have a light behind each diamond which can be turned on or off). Further, you have a switch corresponding to each row of this diamond-grid. When you operate a switch, it will toggle (flip) the lights corresponding to that row.

You are given the current configuration of the lighted diamonds. Gimli challenges Legolas to turn on as many diamonds as possible using EXACTLY K on/off operations of the switches. Since Legolas is an Elf of the Wood and doesn't care much for things that glitter, he instead asks for your help. Note that the same switch (i.e. row) can be chosen multiple times.

Input

The first line contains the number of test cases T. Each test case contains N, M and K on the first line followed by N lines containing M characters each. The ith line denotes the state of the diamonds in the ith row, where '*' denotes a diamond which is on and '.' denotes a diamond which is off.

Output

Output T lines containing the answer for the corresponding case.

Between successive test cases, there should not be any blank lines in the output.

Constraints

1 <= T <= 100

1 <= N, M <= 50

1 <= K <= 100

Sample

Input
2
2 2 1
..
**
2 2 2
..
**

Output
4
2

Notes/Explanation of the Sample:

In the first test case, row 1 can be toggled hence leaving all 4 lights to be in the ON state.

In the second test case, row 1 (or row 2) can be toggled twice, hence maintaining the state of the initial configuration. 


hide comments
rahul11197: 2019-11-07 06:56:19

without sort, you can use the priority queue. TC will be N+K(logN).

dkkv0000: 2019-08-03 21:13:09

easy

hetp111: 2019-05-04 11:33:51

without sort, how?

cutie22by7: 2019-04-27 08:06:06

vkartik97: 2018-07-10 04:22:29
Try this one as well
1
4 20 100
..*....*****.....***
..***..*****.....***
**.....******.....**
***.. ..*****.....**

Pertaining to this test case, you missed a character in the final sequence
if its '.', the answer is 42
if its '*', the answer is 43.

vkartik97: 2018-07-10 04:22:29

Try this one as well
1
4 20 100
..*....*****.....***
..***..*****.....***
**.....******.....**
***.. ..*****.....**

Last edit: 2018-07-10 04:25:56
peregrine: 2018-06-16 17:10:56

Easiest way can be priority_queue

minhthai: 2016-04-08 16:05:14

simple test case:
1
3 3 3
***
***
***
Ouput: 6

Last edit: 2016-04-08 16:05:29
ankit kumar: 2015-08-05 16:21:22

No need to Sort.. AC in one go.. Easy one.!!

CoNtRaDiCtIoN: 2015-05-28 13:53:45

test case to look after
4 4 10
...*
....
....
****
ans = 13

rahul gupta: 2013-01-04 20:24:33

test case which costed me so many wrong answer...

4 5 4
.....
.....
.....
***..

17


Added by:Varun Jalan
Date:2012-12-22
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Varun Jalan - ICPC Asia regionals, Amritapuri 2012