Rào chuồng

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cánh đồng hình chữ nhật có góc $(0, 0)$ và $(A, B)$ . Có $n$ hàng rào dọc (tại $x = a_{i}$ ) và $m$ hàng rào ngang (tại $y = b_{j}$ ), tạo ra $(n + 1) (m + 1)$ vùng.

Để bò di chuyển được khắp cánh đồng, bạn cần gỡ bỏ một số đoạn rào giữa các vùng kề nhau. Chi phí gỡ = chiều dài đoạn rào.

Hãy tìm tổng chiều dài rào tối thiểu cần gỡ để tất cả vùng liên thông.

Dữ liệu vào

Dòng đầu: bốn số nguyên $A$ , $B$ , $n$ , $m$ .
$n$ dòng tiếp: vị trí hàng rào dọc.
$m$ dòng tiếp: vị trí hàng rào ngang.

Dữ liệu ra

Một số nguyên duy nhất — tổng chiều dài tối thiểu.

Ràng buộc

$1 \leq A, B \leq 10^{9}$
$0 \leq n, m \leq 2000$

Ví dụ

Input	Output	Giải thích
15 15 5 2 2 5 10 6 4 11 3	44	Gỡ rào tối ưu: tổng chiều dài = 44.

Bình luận

Không có bình luận tại thời điểm này.