Bessie đang điều hành một dịch vụ taxi cho những con bò khác trong trang trại. Những con bò đang tụ tập tại nhiều vị trí khác nhau dọc theo một hàng rào dài \(M\) (\(1 \le M \le 1\,000\,000\,000\)). Thật không may, chúng đã chán những vị trí hiện tại và mỗi con đều muốn đi tới một nơi khác dọc theo hàng rào. Bessie phải đón từng người bạn tại vị trí xuất phát rồi chở họ tới điểm đến. Xe của Bessie khá nhỏ nên mỗi lần cô chỉ có thể chở một con bò. Bò có thể lên và xuống xe tức thì.

Để tiết kiệm xăng, Bessie muốn giảm thiểu tổng quãng đường cô phải lái xe. Biết vị trí xuất phát và vị trí đích của mỗi con trong số \(N\) con bò (\(1 \le N \le 100\,000\)), hãy xác định quãng đường ít nhất Bessie phải lái. Bessie nhận ra rằng để tiết kiệm xăng nhiều nhất, đôi khi cô có thể cần cho một con bò xuống tại một vị trí không phải điểm đến của nó.

Bessie bắt đầu ở điểm ngoài cùng bên trái của hàng rào, vị trí 0, và phải kết thúc hành trình tại điểm ngoài cùng bên phải của hàng rào, vị trí \(M\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\), cách nhau bởi một dấu cách.

Dòng thứ \(i+1\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(s_i\) và \(t_i\) cách nhau bởi một dấu cách (\(0 \le s_i, t_i \le M\)), lần lượt cho biết vị trí xuất phát và vị trí đích của con bò thứ \(i\).

Dữ liệu ra

In ra một số nguyên duy nhất cho biết tổng quãng đường Bessie phải lái. Lưu ý rằng kết quả có thể không vừa trong một số nguyên 32 bit.

Ví dụ

2 10
0 9
6 5

12

Nguồn

USACO 2013 February Contest, Gold — Problem 2: Taxi

Tác giả đề: Mark Gordon và Richard Peng, 2013.