Cắt Cỏ Nghịch Ngợm

Có $N$ bông hoa trên lưới $[0,T]\times [0,T]$, hoa thứ $i$ ở tọa độ $(x_i,y_i)$. Không có hai bông hoa nào có cùng tọa độ $x$ hoặc $y$.

Bessie muốn chọn tập con lớn nhất các bông hoa nằm trên một đường đi từ $(0,0)$ đến $(T,T)$ chỉ di chuyển sang phải hoặc lên trên. Các hoa được chọn phải có cả tọa độ $x$ và $y$ tăng dần.

Trong tất cả tập con lớn nhất, hãy tìm tập con sao cho diện tích cỏ bị cắt là nhỏ nhất. Diện tích này bằng tổng diện tích hình chữ nhật giữa các điểm liên tiếp (bao gồm $(0,0)$ ở đầu và $(T,T)$ ở cuối):

• $$\sum _{i=0}^{|S|}(x_{i+1}-x_i)(y_{i+1}-y_i)$$

với $(x_0,y_0)=(0,0)$ và $(x_{|S|+1},y_{|S|+1})=(T,T)$.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $T$ ($1\le N\le 3\times {10}^5$, $1\le T\le {10}^6$)
• $N$ dòng tiếp theo: $x_i{y}_i$ ($1\le x_i,y_i\le T-1$)

Dữ liệu ra

Một số nguyên: diện tích cỏ bị cắt nhỏ nhất.

Ràng buộc

• $1\le N\le 3\times {10}^5$, $1\le T\le {10}^6$
• Không có hai hoa nào có cùng tọa độ $x$ hoặc $y$

Ví dụ