Bessie's younger cousins, Ella and Bella, are visiting the farm. Unfortunately,
they have been causing nothing but mischief since they arrived.

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 \times 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 \leq N \leq 2 \cdot 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 \(S\) 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 \(S\). Please help Bessie choose \(S\) so that
the amount of grass cut is as small as possible.

Problem credits: Dhruv Rohatgi

Problem credits: Dhruv Rohatgi

The first line contains \(N\) and \(T\) (\(1 \leq T \leq 10^6\)). Each of the next \(N\)
lines contains the integer coordinates \((x_i, y_i)\) of a flower. It is
guaranteed that \(1 \leq x_i, y_i \leq 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 \leq 3200\).

A single integer, giving the minimum possible amount of cut grass.

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > February > Platinum