공 포장하기 2

시간 제한2초메모리 제한512 MB

요약

K개 색의 공 개수가 주어질 때, 한 상자에 같은 색만 또는 서로 다른 색만 담을 수 있다는 조건 아래 모든 공을 담는 최소 상자 수를 구한다.

문제

공의 색은 모두 $K$ 가지다. 색은 1부터 $K$ 까지의 정수로 나타내며, 색이 $i$ 인 공은 $X_i$ 개 있다.

이 공을 모두 박스에 담아 포장하려고 한다. 박스 하나에는 공을 최대 $K$ 개까지 넣을 수 있다.

한 박스에 들어가는 공의 색은 모두 다르거나, 모두 같아야 한다.

필요한 박스 개수의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 색의 개수 $K$ 가 주어진다. ( $1 \le K \le 100{,}000$ )

둘째 줄에 색이 1인 공부터 색이 $K$ 인 공까지의 개수 $X_1, X_2, \dots, X_K$ 가 공백으로 구분되어 주어진다. ( $1 \le X_i \le 1{,}000{,}000{,}000$ )

첫째 줄에 필요한 박스 개수의 최솟값을 출력한다.