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)$