Problem ID:
rivercity
Points:
2.4 (partial)
Time limit:
1.5s
Memory limit:
256M
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Ở một thành phố nọ, có một con sông chảy ngang qua thành phố. Hai bờ của con sông có dạng hai đường thẳng song song và khoảng cách giữa hai bờ của con sông này là ~l~. Vì con sông rất rộng nên việc di chuyển qua lại hai bên bờ sông là vô cùng khó khăn. Để giải quyết vấn đề này, Sở Giao thông Vận tải đã lên kế hoạch xây dựng ~k~ chiếc cầu bắt qua sông.
Biết rằng:
- Ở bờ phía Bắc của sông, người ta có ~m~ vị trí có thể đặt đầu cầu, mỗi vị trí thứ ~i~ có toạ độ ~a_i~.
- Ở bờ phía Nam của sông, người ta có ~n~ vị trí có thể đặt đầu cầu, mỗi vị trí thứ ~j~ có toạ độ ~b_j~.
- Mỗi chiếc cầu này sẽ có hai đầu cầu, một đầu ở bờ phía Bắc và đầu còn lại ở bờ phía Nam. Mỗi đầu cầu phải được đặt vào một trong các vị trí đã cho.
- Chi phí xây một cây cầu chính là độ dài của cây cầu đó.
Hãy tìm cách dựng ~k~ cây cầu thoả mãn điều kiện trên với tổng chi phí xây dựng nhỏ nhất.
Input
- Dòng đầu tiên chứa ba số nguyên ~m, n, l, k~ ~(1 \le m, n \le 300, 1 \le l \le 10^6, 1 \le k \le min(m, n))~ - lần lượt là số vị trí ở bờ Bắc, số vị trí ở bờ Nam, độ rộng của con sông, và số cây cầu cần xây;
- Dòng thứ hai chứa ~m~ số nguyên phân biệt ~a_1, a_2, ..., a_m~ ~(|a_i| \le 10^6)~ - các vị trí có thể đặt đầu cầu ở bờ Bắc;
- Dòng thứ ba chứa ~n~ số nguyên phân biệt ~b_1, b_2, ..., b_n~ ~(|b_i| \le 10^6)~ - các vị trí có thể đặt đầu cầu ở bờ Nam.
Output
- Một dòng duy nhất ghi tổng chi phí nhỏ nhất có thể để dựng ~k~ cây cầu, dữ liệu được biểu diễn dưới dạng số thực với sai số không quá ~10^{-6}~.
Giới hạn
- Subtask ~1~: ~50\%~ số test có ~m, n \le 10~;
- Subtask ~2~: ~50\%~ số test còn lại không có ràng buộc gì thêm.
Sample Input 1
3 5 7 2
1 3 7
0 2 9 10 12
Sample Output 1
14.142136
Sample Input 2
2 2 4 2
0 1
0 4
Sample Output 2
9.000000
Giải thích
Ở ví dụ ~1~, ta chọn các cặp vị trí ~(1, 1)~ và ~(2, 2)~ để xây cầu. Mỗi cây cầu có chi phí xây dựng là ~5\sqrt{2}~, tổng chi phí là ~10\sqrt{2}~.
Comments