잔디 깎기 장난

Bessie의 어린 사촌 Ella와 Bella가 농장에 놀러 왔다. 안타깝게도 두 사람은 도착한 뒤로 온갖 장난만 치고 있다.

가장 최근의 계획에서 두 사람은 최대한 많은 잔디를 깎기로 했다. 농장의 주요 초지는 한 변의 길이가 $T$인 커다란 정사각형 모양이다. 왼쪽 아래 모서리는 $(0,0)$, 오른쪽 위 모서리는 $(T,T)$이다. 따라서 이 정사각형에는 $(T+1)^2$개의 격자점(좌표가 정수인 점)이 있다.

Ella와 Bella는 둘 다 $(0,0)$에서 출발해 $(T,T)$까지 단위 속력으로 달리며, 각자 매우 날카롭고 잘 늘어나는 철사의 한쪽 끝을 잡을 계획이다. 이 철사가 훑고 지나간 영역의 잔디는 모두 잘린다. Ella와 Bella는 서로 다른 경로를 택할 수 있지만, 각 경로는 격자점에서 격자점으로 위쪽과 오른쪽으로만 이동하는 단계로 이루어진다.

Bessie는 잔디가 너무 많이 잘릴까 걱정한 나머지, Ella와 Bella가 지나는 경로를 제한할 기발한 계획을 세운다. 초지 곳곳에는 맛있는 꽃이 $N$송이 있고($1 \leq N \leq 2 \cdot 10^5$), 각각 서로 다른 격자점에 있다. Bessie는 Ella와 Bella가 모두 반드시 방문해야 할 꽃 $S$송이를 고른다(즉 Ella의 경로도, Bella의 경로도 $S$에 속한 모든 꽃을 방문해야 한다). 경로에 경유지을 최대한 많이 추가하기 위해, Bessie는 $(0,0)$에서 $(T,T)$로 위쪽과 오른쪽으로만 이동하는 소가 방문할 수 있는 꽃들의 부분집합 중에서 $S$를 최대한 크게 고른다.

Ella와 Bella는 $S$에 속한 꽃을 방문해야 한다는 제약 아래에서 깎는 잔디의 양을 최대화하려 한다. 잘리는 잔디의 양이 최소가 되도록 Bessie가 $S$를 고르도록 도와주자.

첫째 줄에 $N$과 $T$가 주어진다($1 \leq T \leq 10^6$). 다음 $N$개 줄에 각각 꽃의 정수 좌표 $(x_i, y_i)$가 주어진다. 모든 $i$에 대해 $1 \leq x_i, y_i \leq T-1$이고, 어떤 두 꽃도 같은 가로줄이나 세로줄에 있지 않음이 보장된다.

전체 테스트 케이스 중 최소 20%에서는 추가로 $N \leq 3200$임이 보장된다.

잘릴 수 있는 잔디 양의 최솟값을 나타내는 정수 하나를 출력한다.

위 예시에서 Bessie가 $(10,3)$과 $(13,11)$에 있는 꽃을 고르는 것이 최적이다. 그러면 최악의 경우 Ella와 Bella는 넓이의 합이 $117$인 직사각형 세 개의 잔디를 깎는다.