Bài 2: GIAO HÀNG (3 điểm)

   Dọc trên tuyến đường tỉnh lộ, con đường dài nhất khu vực, có nhiều ngôi nhà được đánh chỉ số liên tiếp từ 0 đến M. Khoảng cách giữa các ngôi nhà kế cận nhau bằng chính xác 1 đơn vị chiều dài. Hằng ngày Robot giao hàng DeliRo thực hiện hành trình bắt đầu từ nhà số 0, kết thúc ở nhà số M và vận chuyển hàng qua lại giữa các ngôi nhà . Hôm nay có N đơn hàng, mỗi đơn hàng yêu cầu DeliRo lấy hàng từ một ngôi nhà và giao hàng đến một nhà khác. Việc nhận và giao các đơn hàng có thể được thực hiện theo thứ tự bất kỳ. Ví dụ đơn hàng A yêu cầu lấy hàng từ nhà số 3 và giao đến nhà số 7, đơn B từ nhà số 5 đến nhà số 2. DeliRo bắt đầu từ nhà số 0, có thể di chuyển đến nhà số 3 để lấy hàng của đơn A, di chuyển đến nhà số 5 để lấy hàng đơn B, đi ngược lại nhà số 2 để trả hàng cho đơn B, tiếp tục đi đến nhà số 7 trả hàng cho đơn A và đi đến trạm cuối là nhà số M.

   Yêu cầu: Hãy viết chương trình cho biết đoạn đường ngắn nhất mà DeliRo phải thực hiện để bắt đầu từ nhà số 0, giao hàng theo yêu cầu của N đơn hàng và đến trạm cuối là nhà số M. Giả sử khoang chứa hàng của DeliRo có thể chứa rất nhiều hàng.

   Dữ liệu: Vào từ file văn bản GIAOHANG.INP, dòng đầu là hai số nguyên N và M. Dòng thứ i trong N dòng tiếp theo chứa hai số nguyên trong khoảng [0;M] lần lượt là vị trí lấy hàng và giao hàng của đơn hàng thứ i.

Kết quả: Ghi ra file văn bản GIAOHANG.OUT cho biết chiều dài đoạn đường ngắn nhất mà DeliRo phải di chuyển để giao hàng theo yêu cầu của N đơn hàng và đến trạm cuối là nhà số M.

Ràng buộc:

·         *30% test ứng với 30% số điểm của bài có N = 2 và 2 < M ≤ 10⁹

·         *30% test ứng với 30% số điểm của bài có 1 < N ≤ 10 000 và 2 < M ≤ 10⁹

·         *40% test ứng với 40% số điểm của bài có 1 < N ≤ 300 000 và 2 < M ≤ 10⁹