The Great Mixing

Sasha and Kolya은(는) 또다시 Coke를 마시고 취하기로 했다. 이번에는 k가지 종류의 Coke가 있다. i-th 종류는 이산화 탄소 농도 로 특징지어진다. 오늘 Sergiy of Vancouver을(를) 기념하는 파티에서, 이산화 탄소 농도가 인 Coke 한 잔을 준비하기로 했다. 음료는 맛도 있어야 하므로, 잔에는 각 종류의 Coke가 정수 리터만큼만 들어갈 수 있다(일부 종류는 잔에 들어가지 않아도 된다). 또한 잔에 담기는 Coke의 전체 부피를 최소화하려고 한다.

이산화 탄소 농도는 Coke에 들어 있는 이산화 탄소의 부피를 Coke의 전체 부피로 나눈 값으로 정의한다. 두 Coke를 섞으면 이산화 탄소의 부피는 합산되며, Coke의 전체 부피도 합산된다.

이들을 도와 이산화 탄소 농도 인 한 잔을 만드는 데 필요한 최소 자연수 리터를 구한다. 친구들이 각 종류의 Coke를 무제한으로 가지고 있다고 가정한다.

첫째 줄에는 두 정수 n, k (0 ≤ n ≤ 1000, 1 ≤ k ≤ 106)이 주어진다. 이는 각각 친구들이 원하는 이산화 탄소 농도와 Coke 종류의 수이다.

둘째 줄에는 k개의 정수 a1, a2, ..., ak (0 ≤ ai ≤ 1000)이 주어진다. 이는 각 종류 Coke의 이산화 탄소 농도이다. Some Coke 종류가 같은 농도를 가질 수 있다.

이산화 탄소 농도 인 한 잔을 준비하는 데 필요한 최소 자연수 리터를 출력하고, 불가능하면 -1을 출력한다.

첫 번째 예제에서는 종류와 종류의 Coke를 각각 한 리터씩 사용하여 농도 를 만들 수 있다: .

두 번째 예제에서는 종류를 두 리터, 종류를 한 리터 사용하여 농도 를 만들 수 있다: .