바벨

막대 14개와 원판 14개가 주어질 때, 원판을 막대 양쪽에 같은 무게로 올려 만들 수 있는 모든 들어올리기 무게를 구한다.

보통6완전 탐색해시맵동적 계획법조합론아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

동네 체육관에 바벨 봉이 bb개, 원판이 pp개 있다. 들어 올릴 무게를 만들려면 봉을 하나 고르고, 그 봉의 양쪽 끝에 원판을 나누어 끼운다. 한쪽에 끼우는 원판 집합은 비어 있어도 된다. 안전을 위해 양쪽의 무게 합은 반드시 같아야 한다. 양쪽에 올린 원판의 구성은 서로 달라도 되지만 무게 합은 같아야 한다.

원판은 각각 한 번만 쓸 수 있고, 쓰지 않고 남겨 두어도 된다. 들어 올리는 무게는 봉의 무게에 양쪽 원판의 무게를 모두 더한 값이다. 들어 올릴 수 있는 무게를 모두 구하라.

입력

첫 줄에 봉의 개수 bb와 원판의 개수 pp가 주어진다 (1b,p141 \le b, p \le 14). 다음 bb개 줄에는 봉의 무게 xx가 한 줄에 하나씩 주어진다 (1x1081 \le x \le 10^8). 그다음 pp개 줄에는 원판의 무게 yy가 한 줄에 하나씩 주어진다 (1y1081 \le y \le 10^8).

출력

들어 올릴 수 있는 무게를 오름차순으로 한 줄에 하나씩 모두 출력한다. 같은 무게를 두 번 출력하면 안 된다.