В продуктовом магазине рядом с домом Макса началась акция: за покупки посетителям дарят сувениры по мотивам известного мультфильма. Неожиданно, но Макс — рьяный фанат этого мультфильма, поэтому он решил во что бы то ни стало собрать всю коллекцию сувениров.
Макс выяснил у кассира правила акции. Всего в магазине есть $$$N$$$ сувениров $$$M$$$ разных видов; количество сувениров $$$i$$$-го вида — $$$A_i$$$. Каждому покупателю кассир дарит один случайный сувенир.
Макс решил, что потратит все свои сбережения, но пройдёт через кассу столько раз, сколько потребуется, чтобы собрать все виды сувениров. Помогите ему определить минимальное количество покупок, которого будет достаточно, чтобы гарантированно собрать всю коллекцию.