Maryam là một kỹ sư điện đang thiết kế hệ thống dây nối trên một tháp truyền thông. Trên tháp có các điểm kết nối ở những độ cao khác nhau. Mỗi đoạn dây nối hai điểm kết nối, và mỗi điểm có thể được nối với một số lượng tùy ý các đoạn dây. Có hai loại điểm kết nối: đỏ và xanh.

Trong bài toán này, tháp được xem như một đường thẳng. Các điểm kết nối đỏ và xanh nằm tại những tọa độ nguyên không âm trên đường thẳng đó. Độ dài của một đoạn dây bằng khoảng cách giữa hai điểm mà nó nối.

Hãy giúp Maryam tìm tổng độ dài dây nhỏ nhất trong một sơ đồ kết nối thỏa mãn: mỗi điểm kết nối có ít nhất một đoạn dây nối nó với một điểm kết nối khác màu.

Chi tiết cài đặt

Bạn cần cài đặt hàm C++ sau, được khai báo trong tệp wiring.h:

long long min_total_length(std::vector<int> r, std::vector<int> b);

• r: mảng gồm \(n\) phần tử, chứa tọa độ các điểm kết nối đỏ theo thứ tự tăng dần.
• b: mảng gồm \(m\) phần tử, chứa tọa độ các điểm kết nối xanh theo thứ tự tăng dần.

Hàm phải trả về tổng độ dài dây nhỏ nhất trong tất cả các sơ đồ kết nối hợp lệ. Giá trị trả về là số nguyên \(64\) bit, có kiểu long long trong C++.

Ràng buộc

• \(1 \le n,m \le 100\,000\).
• \(0 \le r[i] \le 10^9\) với mọi \(0 \le i \le n-1\).
• \(0 \le b[i] \le 10^9\) với mọi \(0 \le i \le m-1\).
• Mỗi mảng r và b được sắp xếp theo thứ tự tăng dần.
• Tất cả \(n+m\) giá trị trong hai mảng đôi một khác nhau.

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(n\ m\).
• Dòng \(2\): \(r[0]\ r[1]\ \ldots\ r[n-1]\).
• Dòng \(3\): \(b[0]\ b[1]\ \ldots\ b[m-1]\).

Trình chấm mẫu in giá trị trả về của min_total_length trên một dòng duy nhất.

Ví dụ

4 5
1 2 3 7
0 4 5 9 10

10

min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10});