Pha trộn dung dịch

Có $k$ loại dung dịch. Loại thứ $i$ có nồng độ ${\displaystyle \frac{a_i}{1000}}$, và nguồn cung của mỗi loại là không giới hạn.

Bạn muốn pha một cốc dung dịch có nồng độ đúng bằng ${\displaystyle \frac{n}{1000}}$ bằng cách lấy $c_i$ lít dung dịch loại $i$, trong đó mọi $c_i$ đều là số nguyên không âm. Khi trộn, thể tích chất tan và thể tích dung dịch đều cộng dồn, nên nồng độ của cốc thu được là

$$\frac{{\sum }_{i=1}^k{a}_i·c_i}{1000·{\sum }_{i=1}^k{c}_i}.$$

Cốc phải chứa ít nhất $1$ lít dung dịch, tức là $\sum c_i\ge 1$.

Hãy tìm tổng thể tích $\sum c_i$ nhỏ nhất có thể, hoặc cho biết không tồn tại cách pha nào.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$: nồng độ mong muốn (nhân với $1000$) và số loại dung dịch.
• Dòng thứ hai chứa $k$ số nguyên $a_1,a_2,\dots ,a_k$: nồng độ (nhân với $1000$) của từng loại. Các loại khác nhau có thể có cùng nồng độ.

Dữ liệu ra

In ra một số nguyên là tổng số lít nhỏ nhất cần dùng, hoặc $-1$ nếu không thể pha được nồng độ ${\displaystyle \frac{n}{1000}}$.

Ràng buộc

• $0\le n\le 1000$
• $1\le k\le {10}^6$
• $0\le a_i\le 1000$

Ví dụ