Let's move across the x-axis from 0 to $$$MAX_X = 1e4$$$ and maintain the values of the $$$x$$$-th coloumn from the grid. We need to recalculate it efficiently using the $$$x-1$$$-th coloumn somehow. If there is no rectangle having $$$x$$$ as a leftmost or rightmost point, its clear that $$$x$$$-th coloumn is equal to the $$$x-1$$$-th one. Otherwise there are two possible types of actions for $$$x$$$:
- $$$x$$$ is the rightmost coordinate of the rectangle
- $$$x$$$ is the leftmost coordinate of the rectange
For each action of the first type we need to decrease values in the appropriate range by the appropriate cost value. And for the second type actions we need to increase the values in the same way. To do in efficiently you can construct a preffix array for that values and then add it to the $$$x-1$$$-th coloumn and that is — you've got an $$$x$$$-th coloumn. Then just update the maximum and its count.

Complexity is $$$O(MAX_X * MAX_Y + N)$$$
Here is my brief implementation https://ideone.com/82XDr3 . There might be some bugs, but anyway it can help you understand the idea.