Problem

6 /7


Mission Serenity

Problem

The crew of the Serenity interplanetary ship of the class Firefly delivers cargo to various planets of the star system. The ship has a secret cargo hold consisting of N × M cells. Each cell of the cargo compartment has a maximum volume that it can accommodate. It is impossible to fit into the cell a load with a volume greater than the maximum volume of the cell. Only exactly one load can be placed in one cell. 
 
   Serenity Captain Malcolm Reynolds thinks through cargo placement into cells. Help him determine the maximum amount of cargo the captain can deliver.
 
Input
The first line contains numbers N and M (\(1 \leq N, M \leq 40\) ). Each of the following N lines contains M numbers indicating the maximum volume of the corresponding cell. The (N+2)th line contains the number K (\(1 \leq K \leq 2000\)) – the amount of cargo. The (N+3)-th line contains K numbers, the i-th of which is – volume ith cargo. All volumes – natural numbers not exceeding 109.

Imprint
It is required to display one number – the maximum possible amount of cargo that can be delivered.
 
Example
# Input Output
1
3 2
5 10
7 5
5 5
6
9 5 3 5 12 10
 4

time 2000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!