Problem
Phi hành đoàn của Serenity tàu liên hành tinh lớp Firefly vận chuyển hàng hóa đến các hành tinh khác nhau của hệ sao. Con tàu có một hầm hàng bí mật bao gồm N × M tế bào. Mỗi ô của khoang chở hàng có thể tích tối đa mà nó có thể chứa. Không thể lắp vào ô một tải có âm lượng lớn hơn âm lượng tối đa của ô. Chỉ có thể đặt đúng một tải vào một ô.
Sự thanh thản Thuyền trưởng Malcolm Reynolds suy nghĩ về việc sắp xếp hàng hóa vào các ô. Giúp anh ấy xác định khối lượng tối đa của hàng hóa mà thuyền trưởng có thể giao.
Đầu vào
Dòng đầu tiên chứa các số N và M (\(1 \leq N, M \leq 40\) ). Mỗi dòng N sau chứa các số M cho biết thể tích tối đa của ô tương ứng. Dòng thứ (N+2)chứa số K (\(1 \leq K \leq 2000\)) – số lượng hàng hóa. Dòng thứ (N+3) chứa các số K, dòng thứ i là – khối lượng ihàng hóa thứ. Tất cả tập – các số tự nhiên không quá 109.
Dấu ấn
Cần phải hiển thị một số – lượng hàng hóa tối đa có thể được giao.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
3 2
5 10
7 5
5 5
6
9 5 3 5 12 10
|
4 |
Запрещенные операторы: sort