This is a somewhat tricky math problem. There are two key observations necessary to solve this problem fully. The first is that the perimeter of a rectangle with a rectangular corner missing is equal to the perimeter of the original rectangle.

For 40% of the points, we try every single possible rectangle dimension that is no greater than ~R~ by ~C~ to find a minimum-perimeter rectangle with an area that is at least ~K~.

Time complexity: ~\mathcal{O}(RC)~

For 70% of the points, let a rectangle's dimension be a value between ~1~ to ~R~. Then the other dimension can be calculated by division and rounding up. If the other dimension is equal to or less than ~C~, then this rectangle will fit in the grid and should be considered as a possible answer.

Time complexity: ~\mathcal{O}(R)~, although an optimization allows for ~\mathcal{O}(\min(R,C))~

In another approach, we make another key observation, which is that the sheep should all fit in the smallest ~s\cdot s~ rectangle or ~s\cdot (s+1)~ rectangle, if possible. The proof is as follows:

Suppose we have a rectangle with dimensions ~w~ and ~l~, ~w \le l~. If we increase ~w~ by ~1~, then the area increases by ~1\cdot l~. If we increase ~l~ by ~1~, the area increases by ~1\cdot w~. Since ~w \le l~, it is always better to increase ~w~ by ~1~ in order to maximize area. This is true even if the area needs to be increased multiple times.

If there is only ~1~ sheep, only a unit square (~1~ by ~1~ square) is sufficient to surround the sheep with minimum perimeter. Now, suppose we have a square with dimensions ~k~ by ~k~. If we increase one dimension once, the most optimal solution is to form a rectangle with dimensions ~k~ by ~k+1~. If we repeat this process, we will form a square with dimensions ~k+1~ by ~k+1~. From this, we show by induction that the optimal rectangle (fits the most area with minimal perimeter) is in the form of ~s\cdot s~ or ~s\cdot (s+1)~.

Be wary that if a square with a side length ~\min(R,C)~ has less area than ~K~, it is not possible to form a larger square, and thus, the width of the desired rectangle should be equal to ~\min(R,C)~.

For 70% of the points, we follow this proof by starting from a unit square and gradually increasing the sides one at a time until the area of the rectangle is at least ~K~.

Time complexity: ~\mathcal{O}(\min(R,C))~

For 100% of the points, we optimize the proof shown above. We find the dimensions of the smallest square with an area of at least ~K~ by using the square root function. Suppose that this square has dimensions ~x~ by ~x~. We then must check if the rectangle with dimensions ~x~ by ~x-1~ has an area of at least ~K~ as well. Be careful to check if this rectangle does not fit in the ~R~ by ~C~ grid.

Time complexity: ~\mathcal{O}(1)~