'Hush!' said Frodo. 'I think I hear hoofs again.'
They stopped suddenly and stood as silent as tree-shadows, listening. There was a sound of hoofs in the lane, some way behind, but coming slow and clear down the wind. Quickly and quietly they slipped off the path, and ran into the deeper shade under the oak-trees.
The hoofs drew nearer. They had no time to find any hiding-place better than the general darkness under the trees.
- Frodo, Sam and Pippin, when they encounter a Black Rider.
Indeed, the Black Riders are in the Shire, and they are looking for the One Ring. There are N hobbits out in their fields, but when they hear the Riders approaching, or feel the fear cast by their presence, they immediately wish to run and hide in M holes located nearby.
Now, each hole has space for just 1 hobbit; however, once a hobbit reaches a hole, he is able to make room for one more hobbit by digging away at the earth. The time required to make enough space for a second hobbit is C units. Also, each hole CANNOT hold more than 2 hobbits, even after digging. Also note that a hobbit can begin making space for the next hobbit only after he reaches the hole.
You are given the time required to travel from each hobbit's current location to each hole. Find the minimum amount of time it will take before at least K of the hobbits are hiding safely.
Input (STDIN):
The first line contains T, the number of test cases.
The first line of each test case contains 4 integers - N (no of hobbits), M (no of holes), K (minimum number of hobbits to hide) and C (time taken to expand a hole).
The next N lines contain M integers each, denoting the time taken for each hobbit to each hole.
Output (STDOUT):
Output one line per test case which contains the minimum time.
Constraints:
1 <= T <= 6
1 <= N, M <= 100
1 <= K <= min(N, 2 * M)
0 < C < 10,000,000
0 < Time taken by the hobbits to the holes < 10,000,000
Time Limit: 2s
Memory Limit: 64MB
Sample Input:
2
3 3 2 10
9 11 13
2 10 14
12 15 12
4 3 3 8
1 10 100
1 10 100
100 100 6
12 10 10
Sample Output:
10
9
Notes/Explanation of Sample Input:
For the first test case, there are 3 hobbits and 3 holes, and we need to get atleast 2 of them to safety. We can send the first hobbit to the first hole, and the second hobbit to the second hole, thereby taking 10 time units.
For the second test case, we can make hobbit #1 reach hole 1 at time 1, hobbit #2 reach hole 1 at time 9 (by when hobbit #1 would have finished digging the hole), and hobbit #3 reach hole 3 at time 6.
'Hush!' said Frodo. 'I think I hear hoofs again.'
They stopped suddenly and stood as silent as tree-shadows, listening. There was a sound of hoofs in the lane, some way behind, but coming slow and clear down the wind. Quickly and quietly they slipped off the path, and ran into the deeper shade under the oak-trees.
The hoofs drew nearer. They had no time to find any hiding-place better than the general darkness under the trees.
- Frodo, Sam and Pippin, when they encounter a Black Rider.
Indeed, the Black Riders are in the Shire, and they are looking for the One Ring. There are N hobbits out in their fields, but when they hear the Riders approaching, or feel the fear cast by their presence, they immediately wish to run and hide in M holes located nearby.
Now, each hole has space for just 1 hobbit; however, once a hobbit reaches a hole, he is able to make room for one more hobbit by digging away at the earth. The time required to make enough space for a second hobbit is C units. Also, each hole CANNOT hold more than 2 hobbits, even after digging. Also note that a hobbit can begin making space for the next hobbit only after he reaches the hole.
You are given the time required to travel from each hobbit's current location to each hole. Find the minimum amount of time it will take before at least K of the hobbits are hiding safely.
Input (STDIN):
The first line contains T, the number of test cases.
The first line of each test case contains 4 integers - N (no of hobbits), M (no of holes), K (minimum number of hobbits to hide) and C (time taken to expand a hole).
The next N lines contain M integers each, denoting the time taken for each hobbit to each hole.
Output (STDOUT):
Output one line per test case which contains the minimum time.
Constraints:
1 <= T <= 6
1 <= N, M <= 100
1 <= K <= min(N, 2 * M)
0 < C < 10,000,000
0 < Time taken by the hobbits to the holes < 10,000,000
Sample Input:
2
3 3 2 10
9 11 13
2 10 14
12 15 12
4 3 3 8
1 10 100
1 10 100
100 100 6
12 10 10
Sample Output:
10
9
Notes/Explanation of Sample Input:
For the first test case, there are 3 hobbits and 3 holes, and we need to get atleast 2 of them to safety. We can send the first hobbit to the first hole, and the second hobbit to the second hole, thereby taking 10 time units.
For the second test case, we can make hobbit #1 reach hole 1 at time 1, hobbit #2 reach hole 1 at time 9 (by when hobbit #1 would have finished digging the hole), and hobbit #3 reach hole 3 at time 6.
