천칭
시간 제한2초메모리 제한512 MB
기존 추 집합과 목표량들이 주어질 때, 각 목표량을 추들의 부호 있는 부분집합 합으로 나타낼 수 있게 하는 가장 가벼운 추가 추를 구하거나, 0 또는 -1을 출력한다.
문제
실험 화학자인 당신은 천칭과 분말 화학약품의 무게를 재기 위한 추 세트를 가지고 있다.
작업 효율을 위해, 각 양의 측정에는 천칭을 한 번만 사용하는 것으로 충분해야 한다. 한 번에 임의의 개수의 추를 사용할 수 있으며, 화학약품 반대쪽 접시에 놓거나 화학약품과 같은 접시에 놓을 수 있다. 예를 들어, 2와 9 단위의 추가 두 개 있으면, 화학약품 2 단위와 9 단위뿐만 아니라, 둘 다 화학약품 반대쪽 접시에 놓아 11 단위를 잴 수 있고(그림 C-1 왼쪽), 하나를 화학약품과 같은 접시에 놓아 7 단위를 잴 수 있다(그림 C-1 오른쪽). 이것들이 효율적으로 잴 수 있는 유일한 양이다.
그림 C-1 화학약품 11 단위와 7 단위 재기
오늘 재야 할 화학약품 양의 목록이 있다. 그러나 이미 가지고 있는 추 세트만으로는 측정 목록의 모든 양을 효율적으로 잴 수 없을 수 있다. 그렇다면 새 추를 하나만 사서 세트를 보충할 수 있지만, 무거운 추가 더 비싸기 때문에 가능한 한 가벼운 것으로 하고 싶다.
임의의 양의 질량을 가진 추는 시중에 있지만, 음의 질량을 가진 추는 구할 수 없다.
입력
입력은 최대 100개의 데이터셋으로 이루어지며, 각 데이터셋의 형식은 다음과 같다.
n m
a1 a2 ... an
w1 w2 ... wm
데이터셋의 첫 줄에는 n과 m이 있으며, 각각 측정 목록에 있는 양의 개수와 가지고 있는 추 세트의 추 개수이다. 이들은 공백으로 구분된 정수이며 1 ≤ n ≤ 100과 1 ≤ m ≤ 10을 만족한다.
다음 줄에는 측정 목록의 n개 양 a1부터 an까지가 공백으로 구분되어 있다. 각 ai는 1 ≤ ai ≤ 109를 만족하는 정수이고, i ≠ j이면 ai ≠ aj이다.
데이터셋의 세 번째이자 마지막 줄에는 가지고 있는 m개 추의 질량 목록 w1부터 wm까지가 공백으로 구분되어 있다. 각 wj는 1 ≤ wj ≤ 108을 만족하는 정수이다. 두 개 이상의 추가 같은 질량을 가질 수 있다.
입력의 끝은 두 개의 0을 포함한 줄로 표시된다.
출력
각 데이터셋에 대해, 다음과 같이 지정된 정수 하나를 한 줄에 출력한다.
- 추가 추 없이 측정 목록의 모든 양을 잴 수 있으면
0. - 추가 추 하나를 더하면 측정 목록의 모든 양을 잴 수 있게 되는 경우, 그러한 추 중 가장 가벼운 추의 질량. 추가한 추는 108 단위보다 무거울 수 있다.
- 추가 추 하나를 더해도 측정 목록의 모든 양을 절대 잴 수 없으면
-1.