NC24265. [USACO 2019 Feb P]Mowing Mischief
描述
In their latest scheme, they have decided to mow as much grass as they can. The farm's prime grassland is in the shape of large T×T square. The bottom-left corner is (0,0), and the top-right corner is (T,T). The square therefore contains (T+1)^2 lattice points (points with integer coordinates).
Ella and Bella plan to both start at (0,0) and run at unit speed to (T,T) while each holding one end of a very sharp and very stretchy wire. Grass in any area that is swept by this wire will be cut. Ella and Bella may take different paths, but each path consists of only upward and rightward steps, moving from lattice point to lattice point.
Bessie is rather concerned that too much grass will be cut, so she invents a clever plan to constrain the paths Ella and Bella take. There are N yummy flowers (1≤N≤2⋅10^5) scattered throughout the grassland, each on a distinct lattice point. Bessie will pick a set of S flowers that will be required for both Ella and Bella to visit (so Ella's path must visit all the flowers in S, and so must Bella's path). In order to add as many waypoints to these paths as possible, Bessie will choose SS to be as large as possible among subsets of flowers that can be visited by a cow moving upward and rightward from (0,0) to (T,T).
Ella and Bella will try to maximize the amount of grass they cut, subject to the restriction of visiting flowers in SS. Please help Bessie choose SS so that the amount of grass cut is as small as possible.
输入描述
The first line contains N and T (1≤T≤10^6). Each of the next N lines contains the integer coordinates (xi,yi) of a flower. It is guaranteed that 1≤xi,yi≤T−1 for all i, and no two flowers lie on the same horizontal or vertical line.
In at least 20% of the test cases, it is further guaranteed that N≤3200.
输出描述
A single integer, giving the minimum possible amount of cut grass.
示例1
输入:
5 20 19 1 2 6 9 15 10 3 13 11
输出:
117
说明:
In the above example, it is optimal for Bessie to pick the flowers at (10,3) and (13,11). Then in the worst case, Ella and Bella will cut three rectangles of grass with total area 117.