The Great Mixing

题意翻译

有k种可乐，第i瓶可乐的CO2浓度是ai/1000，问要配置出浓度n/1000的可乐，最少需要几瓶可乐。 输入： 第一行n和k。 第二行k个整数，第i个整数表示ai。 输出： 一行，表示最少需要几瓶，无解输出-1。

题目描述

Sasha and Kolya decided to get drunk with Coke, again. This time they have $ k $ types of Coke. $ i $ -th type is characterised by its carbon dioxide concentration . Today, on the party in honour of Sergiy of Vancouver they decided to prepare a glass of Coke with carbon dioxide concentration . The drink should also be tasty, so the glass can contain only integer number of liters of each Coke type (some types can be not presented in the glass). Also, they want to minimize the total volume of Coke in the glass. Carbon dioxide concentration is defined as the volume of carbone dioxide in the Coke divided by the total volume of Coke. When you mix two Cokes, the volume of carbon dioxide sums up, and the total volume of Coke sums up as well. Help them, find the minimal natural number of liters needed to create a glass with carbon dioxide concentration . Assume that the friends have unlimited amount of each Coke type.

输入输出格式

输入格式

The first line contains two integers $ n $ , $ k $ ( $ 0<=n<=1000 $ , $ 1<=k<=10^{6} $ ) — carbon dioxide concentration the friends want and the number of Coke types. The second line contains $ k $ integers $ a_{1},a_{2},...,a_{k} $ ( $ 0<=a_{i}<=1000 $ ) — carbon dioxide concentration of each type of Coke. Some Coke types can have same concentration.

输出格式

Print the minimal natural number of liter needed to prepare a glass with carbon dioxide concentration , or -1 if it is impossible.

输入输出样例

输入样例 #1

400 4
100 300 450 500

输出样例 #1

2

输入样例 #2

50 2
100 25

输出样例 #2

3

说明

In the first sample case, we can achieve concentration  using one liter of Coke of types  and : . In the second case, we can achieve concentration  using two liters of  type and one liter of  type: .

题意翻译

有k种可乐，第i瓶可乐的CO2浓度是ai/1000，问要配置出浓度n/1000的可乐，最少需要几瓶可乐。 输入： 第一行n和k。 第二行k个整数，第i个整数表示ai。 输出： 一行，表示最少需要几瓶，无解输出-1。