Khu sinh thái Funny 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 Dante 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~).

Dante đượ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 Dante độ 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 ~x_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 vườn nhà Dante.

Sample Input 1

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

Sample Output 1

2