[Pre-QNOI 2022#02] Riêng một góc trời

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 2.5s
Memory limit: 512M

Author:
Problem types

Trí vừa xây xong một tầng hầm ở phía dưới ngôi nhà của cậu ấy. Nhờ tài năng thi công chính xác đến từng millimetre nên căn hầm của cậu vô cùng vuông vức. Căn hầm có thể được biểu diễn bằng một hình chữ nhật trên mặt phẳng tọa độ \(\text{Oxy}\) với hai cạnh song song với trục và hai góc đối nhau có tọa độ \((0,0)\) và \((P,Q)\). Để dễ quản lý, Trí sẽ chia nhỏ căn hầm bằng cách xây thêm \(n\) bức tường song song với trục \(\text{Oy}\) và \(m\) bức tường song song với trục \(\text{Ox}\).

Bức tường thứ \(i\) song song với trục \(\text{Oy}\) sẽ nằm trùng với đường thẳng \(x=a_i\) (với \(0<a_i<P\)). Bức tường này có điểm bắt đầu là \((a_i, 0)\) và điểm kết thúc là \((a_i, Q)\). Có thể xem bề dày bức tường không đáng kể.

Bức tường thứ \(j\) song song với trục \(\text{Ox}\) sẽ nằm trùng với đường thẳng \(y=b_j\) (với \(0<b_j<Q\)). Bức tường này có điểm bắt đầu là \((0, b_j)\) và điểm kết thúc là \((P, b_j)\). Tương tự, có thể xem bề dày bức tường không đáng kể.

Sau khi xây xong \(n+m\) bức tường kể trên, dễ thấy căn hầm của Trí đã được chia thành \((n+1)(m+1)\) phòng nhỏ. Đột nhiên, Trí cảm thấy việc thiết kế mỗi phòng gồm bốn bức tường trùng trùng vây quanh tứ phía như vậy tạo ra cảm giác rất ngột ngạt. Vì vậy, cậu đã lên kế hoạch phá bỏ một số đoạn tường con (một đoạn tường con là phần tường ngăn cách hai phòng kề nhau) sao cho từ một phòng bất kỳ, ta có thể di chuyển sang tất cả các phòng còn lại trong căn hầm mà không bị cản trở bởi một đoạn tường nào. Nói cách khác, khi đó tất cả \((n+1)(m+1)\) phòng đã "liên thông" cùng nhau.

Để trực quan hơn, bạn có thể hình dung hình dưới đây là một ví dụ về kết cấu của căn hầm tại thời điểm Trí thi công xong \(n+m\) bức tường:

before

Và đây là kết cấu tương ứng sau khi Trí thực hiện phá bỏ một số đoạn tường (được tô nhạt lại) để các phòng liên thông cùng nhau:

after

Bạn hãy lập trình để chọn giúp Trí những đoạn tường cần phá sao cho tổng độ dài của chúng là nhỏ nhất có thể nhé! (tất nhiên là bạn không được phép phá các đoạn tường ngoài rìa căn hầm để đảm bảo an toàn)


Input

Dòng đầu chứa bốn số nguyên dương \(P, Q, n\) và \(m\) \((1\leq P,Q\leq 10^9)\).

Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa số nguyên dương \(a_i\). Tất cả các giá trị \(a_i\) đều phân biệt.

Dòng thứ \(j\) trong \(m\) dòng tiếp theo chứa số nguyên dương \(b_j\). Tất cả các giá trị \(b_j\) đều phân biệt.


Output

Gồm một số nguyên là tổng độ dài nhỏ nhất của các đoạn tường ta cần phá bỏ để giúp các phòng liên thông với nhau.


Ví dụ

Sample input
15 16 5 2
3
5
11
6
7
9
3
Sample output
45

Ràng buộc

  • Subtask 1 (80% số điểm): \(n,m\leq 2500\).
  • Subtask 2 (20% số điểm): \(n,m\leq 25000\).