Khu sinh thái Hạ Thảo chuẩn bị tiếp đón một đoàn khách đến tham quan ~m~ giống cây mới (được đánh số từ ~1~ đến ~m~) do nhà khoa học Gia Phúc lai ghép được. Có ~n~ chậu cây, mỗi chậu trồng ~1~ loại cây trong số ~m~ loại giống trên ~(n \le m)~. Có thể coi các cây được trồng trên một đường thẳng trên trục số: chậu thứ ~i~ đặt ở tọa độ ~x_i~ và trồng loại cây ~a_i~ ~(1 \le a_i \le m)~. Hướng dẫn viên được chỉ định sẽ dẫn đoàn khách đi tham quan. Do khách đã đi khảo sát ở nhiều nơi nên họ muốn đi một quãng đường có độ dài ngắn nhất tính từ vị trí cây được thăm đầu tiên để có thể thăm được tất cả ~m~ loại giống cây mới có trong vườn.

Yêu cầu:

Hãy chỉ ra cho anh hướng dẫn viên độ dài ngắn nhất mà đoàn khách cần di chuyển để có thể thăm được hết m loại giống cây mới này.

Dữ liệu vào:

Cho từ file văn bản THAMQUAN.INP:

• Dòng đầu gồm ~2~ số ~n, m~ ~(n \le 10^5; m \le 10^5)~.

• ~n~ dòng tiếp theo, mỗi dòng gồm ~2~ số ~x_i, a_i~ là tọa độ và loại cây trồng tại ~x_i~ ~(0 \le x_i \le 10^9, 0 \le a_i \le m)~.

Dữ liệu ra:

Ghi ra file văn bản THAMQUAN.OUT gồm ~1~ số duy nhất là khoảng cách ngắn nhất mà đoàn khách cần di chuyển để có thể thăm được tất cả các loại cây mới trong khu du lịch.

Ví dụ:

Input

7 3
25 2
26 1
15 1
22 3
20 1
30 1
27 3

Output

2