Hàng Rào Chia Ô

Cho một mảnh đất hình chữ nhật có kích thước $A\times B$. Trên mảnh đất này có $N$ hàng rào dọc (song song với cạnh chiều cao) và $M$ hàng rào ngang (song song với cạnh chiều rộng), chia mảnh đất thành $(N+1)\times (M+1)$ ô hình chữ nhật.

Hàng rào dọc thứ $i$ nằm tại vị trí $x_i$ ($0<x_i<A$) và kéo dài toàn bộ chiều cao $B$. Hàng rào ngang thứ $j$ nằm tại vị trí $y_j$ ($0<y_j<B$) và kéo dài toàn bộ chiều rộng $A$.

Bạn muốn dỡ bỏ một số đoạn hàng rào sao cho tất cả các ô đều thông với nhau (từ bất kỳ ô nào có thể di chuyển sang bất kỳ ô nào khác). Mỗi hàng rào dọc có độ dài $B$, mỗi hàng rào ngang có độ dài $A$, nhưng khi dỡ bỏ, bạn chỉ cần dỡ một đoạn trên hàng rào đó để nối hai ô liền kề (đoạn dỡ có độ dài bằng kích thước của ô theo chiều vuông góc).

Cụ thể, để nối hai ô liền kề theo chiều ngang (cùng hàng, ngăn cách bởi một hàng rào dọc), chi phí bằng chiều cao của ô đó (khoảng cách giữa hai hàng rào ngang liền kề). Để nối hai ô liền kề theo chiều dọc (cùng cột, ngăn cách bởi một hàng rào ngang), chi phí bằng chiều rộng của ô đó (khoảng cách giữa hai hàng rào dọc liền kề).

Hãy tìm tổng độ dài hàng rào nhỏ nhất cần dỡ bỏ để tất cả các ô thông nhau.

Dữ liệu vào

• Dòng đầu: bốn số nguyên $A$, $B$, $N$, $M$.
• Dòng thứ hai: $N$ số nguyên $x_1,x_2,\dots ,x_N$ — vị trí các hàng rào dọc.
• Dòng thứ ba: $M$ số nguyên $y_1,y_2,\dots ,y_M$ — vị trí các hàng rào ngang.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng độ dài hàng rào nhỏ nhất cần dỡ bỏ.

Ràng buộc

• $1\le A,B\le {10}^9$
• $1\le N,M\le 2000$ (trong một số test, $N,M\le 25000$)
• Các vị trí hàng rào đôi một phân biệt và nằm trong khoảng hợp lệ.

Ví dụ

Giải thích ví dụ 1:

Mảnh đất $15\times 15$ được chia bởi 5 hàng rào dọc tại vị trí $\{2,4,5,6,10\}$ và 2 hàng rào ngang tại vị trí $\{3,11\}$.

Các khoảng cách giữa các hàng rào dọc (sau khi sắp xếp: $0,2,4,5,6,10,15$) là: $2,2,1,1,4,5$.

Các khoảng cách giữa các hàng rào ngang (sau khi sắp xếp: $0,3,11,15$) là: $3,8,4$.

Cần dỡ bỏ tổng cộng $44$ đơn vị hàng rào để nối thông toàn bộ $6\times 3=18$ ô.

Ghi chú

Bài toán tương đương với tìm cây khung nhỏ nhất (MST) trên đồ thị lưới $(N+1)\times (M+1)$ đỉnh, trong đó trọng số cạnh giữa hai ô liền kề là kích thước của ô theo chiều vuông góc với hàng rào ngăn cách chúng.