Задача . Mowing Mischief

Они решили скосить как можно больше травы. Травяное пастбище представляет из себя квадрат \(T \times T\). Левый нижний угол квадрата имеет координаты \((0,0)\), а правый верхний угол имеет координаты \((T,T)\). Поэтому квадрат содержит \((T+1)^2\) точек решётки. (точки с целочисленными координатами).

Элла и Белла обе планируют начать в точке \((0,0)\) и двигаться с постоянной единичной скоростью в точку \((T, T)\), каждая держит в руках очень острую проволоку. Трава в области, которую прошла эта проволока, будет срезана. Елла и Белла имеют разные пути, но они состоят из шагов вверх и вправо, от одной точки решётки к другой точке решётки.

Бесси беспокоится, что будет скошено слишком много травы, поэтому она придумала хитроумный план ограничить пути Эллы и Беллы. Имеется \(N\) вкуснейших цветков, \((1 \leq N \leq 2 \cdot 10^5\)) разбросанных по пастбищу, каждый размещён в различной точке решётки. Беси выбрала множество из \(S\) цветков, и потребовала от Беллы и Эллы, чтобы они обязательно посетили точки цветков. То есть, путь Эллы должен пройти через эти \(S\) точек, также как и путь Беллы. Бесси выбрала \(S\) как максимально возможное среди всех подмножеств цветков, которое можно посетить на пути из \((0,0)\) в \((T,T)\), двигаясь только вверх или вправо.

Элла и Белла стараются максимизировать количество травы, которую они выкосят, посетив указанные \(S\) цветков. Помогите Беси выбрать \(S\) таким, чтобы количество выкошенной травы было минимально возможным.

117