eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Розмін монет

Розмін монет

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Ви працюєте на касі на веселому ярмарку, і у Вас є різні номінали монет. Монети кожного номіналу доступні у нескінченній кількості. Вартість кожного номіналу відома. Визначте кількість способів, якими можна сплатити задану суму, використовуючи монети наявних номіналів.

Наприклад, якщо у Вас є 4 номінали монет вартістю 8, 3, 1, 2, то суму 3 можна видати такими способами: \{1, 1, 1\}, \{1, 2\} та \{3\}.

Вхідні дані

Перший рядок містить два цілих числа: суму n~(1 \le n \le 250) і кількість номіналів монет m~(1 \le m \le 50). Другий рядок містить m цілих чисел c_i~(1 \le c_i \le 50), що описують вартість номіналів монет. Усі значення c_i різні.

Вихідні дані

Виведіть кількість способів, якими можна сплатити суму n.

Приклад

Вхідні дані #1
4 3
1 2 3
Вихідні дані #1
4
Вхідні дані #2
10 4
2 5 3 6
Вихідні дані #2
5