English · Original
Chinese · Translation
Formal · Original
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.
## Input
The first line contains two integers _n_, _k_ (0 ≤ _n_ ≤ 1000, 1 ≤ _k_ ≤ 106) — 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.
## Output
Print the minimal natural number of liter needed to prepare a glass with carbon dioxide concentration , or _\-1_ if it is impossible.
[samples]
## Note
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: .
Sasha 和 Kolya 再次决定用可乐醉酒。这次他们有 #cf_span[k] 种可乐。第 #cf_span[i] 种可乐的二氧化碳浓度为 #cf_span[a_i]。今天，在为温哥华的 Sergiy 庆祝的派对上，他们打算调制一杯二氧化碳浓度为 #cf_span[n] 的可乐。饮料还必须美味，因此玻璃杯中每种可乐的体积只能是整数升（某些类型可以不使用）。此外，他们希望最小化可乐的总体积。
二氧化碳浓度定义为可乐中二氧化碳的体积除以可乐的总体积。当你混合两种可乐时，二氧化碳的体积相加，可乐的总体积也相加。
请帮助他们，找出调制出二氧化碳浓度为 #cf_span[n] 的可乐所需的最小正整数升数。假设朋友拥有每种可乐的无限量。
第一行包含两个整数 #cf_span[n], #cf_span[k] (#cf_span[0 ≤ n ≤ 1000], #cf_span[1 ≤ k ≤ 10^6]) —— 朋友想要的二氧化碳浓度和可乐类型的数量。
第二行包含 #cf_span[k] 个整数 #cf_span[a_1, a_2, ..., a_k] (#cf_span[0 ≤ a_i ≤ 1000]) —— 每种可乐的二氧化碳浓度。某些可乐类型可能具有相同的浓度。
请输出调制出二氧化碳浓度为 #cf_span[n] 的可乐所需的最小正整数升数，如果不可能则输出 _-1_。
在第一个样例中，我们可以使用一升第 #cf_span[1] 种和一升第 #cf_span[3] 种可乐来实现浓度：#lt.eq((100 + 450) / (1 + 1), 275)。
在第二个样例中，我们可以使用两升第 #cf_span[1] 种和一升第 #cf_span[2] 种可乐来实现浓度：#lt.eq((2 \cdot 100 + 1 \cdot 25) / (2 + 1), 75)。
## Input
第一行包含两个整数 #cf_span[n], #cf_span[k] (#cf_span[0 ≤ n ≤ 1000], #cf_span[1 ≤ k ≤ 10^6]) —— 朋友想要的二氧化碳浓度和可乐类型的数量。第二行包含 #cf_span[k] 个整数 #cf_span[a_1, a_2, ..., a_k] (#cf_span[0 ≤ a_i ≤ 1000]) —— 每种可乐的二氧化碳浓度。某些可乐类型可能具有相同的浓度。
## Output
请输出调制出二氧化碳浓度为 #cf_span[n] 的可乐所需的最小正整数升数，如果不可能则输出 _-1_。
[samples]
## Note
在第一个样例中，我们可以使用一升第 #cf_span[1] 种和一升第 #cf_span[3] 种可乐来实现浓度：#lt.eq((100 + 450) / (1 + 1), 275)。在第二个样例中，我们可以使用两升第 #cf_span[1] 种和一升第 #cf_span[2] 种可乐来实现浓度：#lt.eq((2 \cdot 100 + 1 \cdot 25) / (2 + 1), 75)。
Let $ n \in \mathbb{Z}_{\geq 0} $ be the target carbon dioxide concentration, and $ k \in \mathbb{Z}_{>0} $ the number of Coke types. Let $ a_1, a_2, \dots, a_k \in \mathbb{Z}_{\geq 0} $ be the carbon dioxide concentrations of each type.
We seek non-negative integers $ x_1, x_2, \dots, x_k \in \mathbb{Z}_{\geq 0} $, not all zero, minimizing $ \sum_{i=1}^k x_i $, subject to:
$$
\frac{\sum_{i=1}^k a_i x_i}{\sum_{i=1}^k x_i} = n
$$
Equivalently:
$$
\sum_{i=1}^k (a_i - n) x_i = 0
$$
Let $ b_i = a_i - n $ for $ i = 1, \dots, k $. Then the constraint becomes:
$$
\sum_{i=1}^k b_i x_i = 0
$$
with $ x_i \in \mathbb{Z}_{\geq 0} $, and we minimize $ \sum_{i=1}^k x_i $ over all non-zero solutions.
If no such non-zero solution exists, output $ -1 $.
---
**Formal Problem Statement:**
Given integers $ n \in [0, 1000] $, $ k \in [1, 10^6] $, and $ a_1, \dots, a_k \in [0, 1000] $, define $ b_i = a_i - n $ for $ i = 1, \dots, k $.
Find the minimal $ s \in \mathbb{Z}_{>0} $ such that there exist $ x_1, \dots, x_k \in \mathbb{Z}_{\geq 0} $, not all zero, with:
$$
\sum_{i=1}^k x_i = s \quad \text{and} \quad \sum_{i=1}^k b_i x_i = 0
$$
If no such $ s $ exists, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "C. The Great Mixing",
"description": {
"content": "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 Sergi",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF788C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 Sergi...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Sasha 和 Kolya 再次决定用可乐醉酒。这次他们有 #cf_span[k] 种可乐。第 #cf_span[i] 种可乐的二氧化碳浓度为 #cf_span[a_i]。今天，在为温哥华的 Sergiy 庆祝的派对上，他们打算调制一杯二氧化碳浓度为 #cf_span[n] 的可乐。饮料还必须美味，因此玻璃杯中每种可乐的体积只能是整数升（某些类型可以不使用）。此外，他们希望最小化可乐的总体积。\n\n...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ n \\in \\mathbb{Z}_{\\geq 0} $ be the target carbon dioxide concentration, and $ k \\in \\mathbb{Z}_{>0} $ the number of Coke types. Let $ a_1, a_2, \\dots, a_k \\in \\mathbb{Z}_{\\geq 0} $ be the carbon...",
"is_translate": false,
"language": "Formal"
}
]
}