У вас есть набор из \(n\) гирек. Вам известно, что они весят \(a_1\), \(a_2\), ..., \(a_n\) граммов, но вы не знаете, какая гирька сколько весит: для вас они неотличимы друг от друга.
Ваш друг знает точный вес каждой гири, и вы можете попросить его дать вам набор из \(k\) гирек с суммарным весом \(m\) (параметры \(k\) и \(m\) выбираете вы сами), и ваш друг укажет вам на какой-нибудь подходящий набор гирек, если такой вообще есть.
Вы можете спросить вашего друга лишь один раз. У какого наибольшего числа гирек вы можете узнать точный вес после этого запроса?
Выходные данные
Выведите единственное число — максимальное количество гирек, вес которых вы можете узнать, один раз спросив друга.
Примечание
В первом примере мы можем попросить набор из двух гирек с суммарным весом \(4\), и единственное, что мы можем получить — \(\{2, 2\}\).
Получить такой же результат можно, попросив набор из двух гирек с суммарным весом \(5\), тогда нам дадут \(\{1, 4\}\). Отсюда мы можем заключить, что каждая из двух оставшихся гирь имеет вес \(2\).
Во втором примере мы можем попросить набор из двух гирек с суммарным весом \(8\) и получить \(\{4, 4\}\). Можно доказать, что нельзя за один запрос узнать веса трех гирек, но мы не будет приводить доказательство здесь.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 4 2 2
|
2
|
|
2
|
6
1 2 4 4 4 9
|
2
|