An impurity at $(x,y)$ will be counted towards the melting point only if the top left corner of the plate is between $(x-R,y-C)$ and $(x,y)$.

The plate will only contain the impurity (red) if its top left corner (black) is inside the blue box.

Draw the bounding rectangle of each impurity. Each rectangle has a value equal to the impurity strength. Find the highest possible total value of rectangles covering a point.

To solve this problem, store the left and right edges of each rectangle and sort them by $x$ coordinate. Perform a line sweep across the $x$ axis. Store the value of each point on the $y$ axis using a segment tree. When a left edge from $y_1$ to $y_2$ of a rectangle of value $v$, add $v$ to the segment tree from $y_1$ to $y_2$. When you reach a right edge, subtract $v$. Each time you add or subtract an edge, also find the maximum value in the segment tree. The maximum of these maximums will be your answer.

Coordinate compress the $y$ values because they can be up to ${10}^9$.

Tips:

• You cannot cut outside of the gem, all edges of your cut must be between $(1,1)$ and $(n,m)$
• Some impurities have negative values, so in some cases, it may be the best option to look for a pure fragment
• Make sure you include all impurities inside your cut when adding up the values, even the negative ones

Time Complexity: $\mathcal{O}(K\log M)$