cho.sh
Notes
Loading...

Atomic Energy

Time limit

2s

Memory limit

128 MB

Problem

Each atom can be in one of several energy states, and each state is represented by the amount of energy the atom has in that state. When an atom changes from a higher energy state to a lower one, it emits one proton whose energy is exactly the difference between the two states. Conversely, to change from a lower energy state to a higher one, it must absorb one proton with that same energy.

After long research, scientists know the energy of every state of this atom. They also know every possible energy that a proton may have. For the atom considered in this problem, each single state change uses exactly one proton, either absorbed or emitted. Between any two energy states there is at most one state-change route when routes that repeat a state are ignored. Therefore, if energy states are vertices and one-step changes are edges, the resulting graph is a forest.

Scientists prepare as many atoms and protons as they need, adjust the atoms' energy states, and then put the atoms into a container. The container is unsafe if two atoms are in the same energy state, or if one atom can absorb or emit exactly one proton and become equal to another atom's energy state.

Choose the energy states of the atoms placed in the container so that the container is safe and the sum of their energies is as large as possible. Given the energy of each state and the possible proton energies, compute this maximum total energy.

Input

The first line contains two integers N and M (1 <= N <= 200, 1 <= M <= 200).

Each of the next N lines contains the energy of one atomic energy state. No two states have the same energy.

Each of the next M lines contains one possible proton energy. Every energy value is a natural number not greater than 1,000,000.

Output

Print the maximum possible sum of energies.