LIGHT - Hệ thống đèn
Giới hạn- Thời gian: 0.286s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Khu vực đặt các bể xăng của một Tổng Công Ty Xăng Dầu có dạng một hình chữ nhật được chia thành m * n ô vuông. Các ô vuông được đánh tọa độ 1 -> m từ trên xuống, 1 -> n từ trái sang.
Tại k ô của lưới có đặt các bể xăng. Người ta cần xây dựng một hệ thống đèn pha chiếu sáng, mỗi đèn chỉ chiếu dọc theo hoặc là hàng hoặc là cột của lưới ô vuông sao cho mỗi bể chứa xăng phải được chiếu sáng bởi ít nhất một đèn pha chiếu dọc theo hàng hoặc cột chứa nó. Biết:
- ai là chi phí xây dựng đèn chiếu sáng dọc theo hàng.
- bj là chi phí xây dựng đèn chiếu sáng dọc theo cột.
Yêu cầu: Tìm cách xây dựng hệ thống đèn với tổng chi phí xây dựng là nhỏ nhất.
Input
- Dòng đầu tiên chứa 3 số nguyên dương m, n, k (m, n <= 100).
- Dòng thứ hai chứa m số nguyên a1, a2, ..., am.
- Dòng thứ ba chứa n số nguyên b1, b2, ..., bn.
- Dòng thứ i trong k dòng tiếp theo chứa tọa độ của bể xăng thứ i.
Output
Một dòng duy nhất ghi tổng chi phí theo cách xây dựng tìm được.
Example
Input: 2 3 4 15 17 2 4 6 1 1 2 2 2 3 2 1 Output: 12
- Người up: dtmp