시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB273784230.435%

문제

잘 알려져 있듯, 각각의 원자들은 어떤 특정한 에너지 상태(혹은 에너지 준위)에 놓일 수 있다. 각각의 상태는 그 상태에서 그 원자가 갖는 에너지로 나타낼 수 있다. 어떤 원자가 높은 에너지 상태에서 낮은 에너지 상태로 변할 때, 두 상태의 에너지 차이만큼의 에너지를 갖는 양성자가 방출된다. 역으로, 낮은 에너지 상태에서 높은 에너지 상태로 변하기 위해서는, 두 상태의 에너지 차이만큼의 에너지를 갖는 양성자가 필요하다.

과학자들은 오랜 연구를 통해서 원자의 각 에너지 상태에서의 에너지를 알아낼 수 있었다. 또한, 하나의 양성자가 가질 수 있는 에너지의 종류들도 모두 알아낼 수 있었다. 또한 이 문제에서 다루게 될 원자의 경우에는, 에너지 상태가 변할 때 오직 한 개의 양성자만이 출입할 수 있음을 알게 되었다. 또한 원자가 어떤 특정 에너지 상태(A)에서 다른 에너지 상태(B)로 변할 수 있는 방법은 한 가지 뿐이고, 이 방법을 역으로 적용(양성자를 받아들인 경우는 양성자를 내쏘고, 양성자를 내쏘는 경우는 양성자를 받아들임)하면 B에서 A로도 상태가 변할 수 있음을 알게 되었다. 물론, A → B → C → B → C → D 와 같은 경우처럼 같은 상태를 반복하는 경우는 고려하지 않는다.

예를 들어 세 개의 에너지 상태를 갖는 원자가, 각 상태에서 2, 4, 6만큼의 에너지를 갖는다고 하자. 또한 실험을 통해서, 양성자가 가질 수 있는 에너지가 2, 3임을 알게 되었다고 하자. 이 경우 원자는 양성자를 받아들이며 2 → 4 → 6의 상태로 변할 수 있고, 반대로 양성자를 내쏘며 6 → 4 → 2의 상태로 변할 수도 있다.

과학자들은 이러한 원자를 가지고 실험을 시작했다. 우선 실험을 위해서 몇 개(제한 없음)의 원자와 몇 개(제한 없음)의 양성자를 준비하고, 이 양성자들을 이용하여 각 원자의 에너지 상태를 조절한다. 에너지 상태가 다 조절된 후에는 이 원자들을 컨테이너 안에 집어넣고 관찰을 하게 된다. 이때, 컨테이너 안에 들어간 원자들이 서로 같은 에너지 상태에 있거나, 어떤 한 개의 원자가 한 개의 양성자를 받아들이거나 내쏘아서 다른 원자와 같은 에너지 상태에 도달할 수 있다면, 이 경우는 실험에서 위험이 발생할 수 있다. 따라서 이러한 경우는 허용되지 않는데, 그러면서도 컨테이너 안의 원자들의 에너지들의 총 합이 최대가 되도록 하려 한다.

원자의 각 에너지 상태에서의 에너지와 양성자가 가질 수 있는 에너지가 주어졌을 때, 컨테이너 안의 원자들의 에너지들의 총 합의 최대를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), M(1 ≤ M ≤ 200)이 주어진다. 다음 N개의 줄에는 원자의 각 에너지 상태에서의 에너지가 주어진다. 물론 두 상태에서의 에너지가 같은 경우는 없다. 다음 M개의 줄에는 양성자가 가질 수 있는 에너지가 주어진다. 각 에너지는 1,000,000이하의 자연수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

3 2
2
4
6
2
3

예제 출력 1

8