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 종류의 수가 주어진다.

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

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

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

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