Khu sinh thái Quỳnh Nhai thuộc huyện Quỳnh Nhai tỉnh Sơn La 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 Nguyễn Hoài An 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 \ge 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~).

Nguyễn Hoài An đượ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ỉ cho Nguyễn Hoài An độ 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.

Input

• 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 ~i~ (~0 \le x_i \le 10^9, 0 < a_i \le m~).

Output

• Ghi ra 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 sinh thái Quỳnh Nhai.

Sample Input 1

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

Sample Output 1

2