## Editorial for Topium

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

An impurity at will be counted towards the melting point only if the top left corner of the plate is between and .

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 coordinate. Perform a line sweep across the axis. Store the value of each point on the axis using a segment tree. When a left edge from to of a rectangle of value , add to the segment tree from to . When you reach a right edge, subtract . 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 values because they can be up to .

Tips:

• You cannot cut outside of the gem, all edges of your cut must be between and
• 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: