Kingdoms
Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1 Accepted Submission(s): 0
Problem Description
The former king of Gridland -- CR -- has just passed away, leaving his K sons that all desire the throne. Then the war of succession breaks out and the K-King era begins.
Gridland is a rectangle of N*M, with each grid unit as a city. Each city supports one and only one of the K kings as its leader. Cities supporting the same king will always endeavor to establish a kingdom through fighting the rival, and they will not stop until they establish a kingdom satisfying the following rules:
1. The kingdom is a rectangle on the map.
2. Every city on the Gridland supporting that king should be inside the kingdom.
Sadly, through the process of establishing a kingdom, once the opposite cities find that an overlapping of domain is unavoidable, they will inevitably engage in a conflict.
Sometimes for a temporary benefit a bunch of kings may ally into a party. It is certain that one king can only take part in one party at one time, and the cities following a king will correspondingly support the party he joins.
Rather than fighting each other fiercely, cities supporting the same party cooperate and strive to establish a kingdom of the whole party.
Such kingdoms follow the similar rules:
1. The kingdom is a rectangle on the map.
2. Every city on the Gridland supporting that party should be inside the kingdom.
And the fighting trigger with other kingdoms is exactly the same as the above one.
A established kingdom is called stable if and only if:
1. No city in the kingdom has to fight with another kingdom..
2. If the kingdom stands for a party, the party must never have more than R kings.
Now, your job is to find the largest possible stable kingdom. By 'largest' we mean the one with the largest number of cities.
Gridland is a rectangle of N*M, with each grid unit as a city. Each city supports one and only one of the K kings as its leader. Cities supporting the same king will always endeavor to establish a kingdom through fighting the rival, and they will not stop until they establish a kingdom satisfying the following rules:
1. The kingdom is a rectangle on the map.
2. Every city on the Gridland supporting that king should be inside the kingdom.
Sadly, through the process of establishing a kingdom, once the opposite cities find that an overlapping of domain is unavoidable, they will inevitably engage in a conflict.
Sometimes for a temporary benefit a bunch of kings may ally into a party. It is certain that one king can only take part in one party at one time, and the cities following a king will correspondingly support the party he joins.
Rather than fighting each other fiercely, cities supporting the same party cooperate and strive to establish a kingdom of the whole party.
Such kingdoms follow the similar rules:
1. The kingdom is a rectangle on the map.
2. Every city on the Gridland supporting that party should be inside the kingdom.
And the fighting trigger with other kingdoms is exactly the same as the above one.
A established kingdom is called stable if and only if:
1. No city in the kingdom has to fight with another kingdom..
2. If the kingdom stands for a party, the party must never have more than R kings.
Now, your job is to find the largest possible stable kingdom. By 'largest' we mean the one with the largest number of cities.
Input
Input contains multiple cases. Each case consists of:
Line 1:Two integers : N and M (1<= N, M <=1000)
Line 2:Two integers : K and R (1<=K<=1000)
Line 3..N+2: M integers each line. the jth integer on the i+2th line will be between 1 and k, indicating which king that city supports.
Line 1:Two integers : N and M (1<= N, M <=1000)
Line 2:Two integers : K and R (1<=K<=1000)
Line 3..N+2: M integers each line. the jth integer on the i+2th line will be between 1 and k, indicating which king that city supports.
Output
For each case, output one line containing an integer that is the area of the largest possible stable kingdom.
Sample Input
3 3 5 3 4 1 1 2 3 1 2 2 5 10 10 13 5 1 1 1 4 4 4 4 4 3 11 1 1 1 4 4 4 4 4 11 3 1 1 1 2 2 2 2 2 3 3 1 1 1 2 2 2 2 2 3 11 1 1 1 2 2 2 2 2 11 11 1 1 1 2 2 2 2 2 3 11 1 1 1 6 6 6 7 7 3 3 1 1 1 6 6 6 7 7 3 3 5 5 5 5 10 13 8 12 9 9 5 5 5 5 13 10 8 8 9 9 2 2 2 1 2 2 2 1
Sample Output
1 64 0