프로그램 명: coci_ljubomora
제한시간: 1 초

[요약] 공기돌 공장은 유치원에 공기돌 박스를 기증 했다. 각 박스는 M 개의 색 중에 하나이다.

운영자는 그룹에 있는 N 명의 아이들에게 모든 박스를 분배하는 것이 필요하다.. 어떤 아이들은 박스를 하나도 받지 않을수도 있지만 , 다른 색의 박스를 원하지 않는다. 즉 아이들은 같은 색의 박스를 가진다.

운영자는 또한 아이들이 다른 사람들이 너무 많은 박스를 가진다면 질투를 느낀다는 것을 안다.

우리는 그룹의 질투레벨을 아이들에게 준 박스의 최대수로 정의할 것이다. 질투레벨을 최소화 하도록 박스를 나누는 방법을 구하는 것이 문제이다.

예를 들어 , 4 개의 빨간색과 7 개의 파란색 , 5 명의 아이들에게 나누어주는 경우 우리는 질투레벨 3 으로 다음과 같이 나누어 줄 수 있고 이 값이 최소 이다. RR, RR, BB, BB, BBB

A marble factory has donated a large box of marbles to a kindergarten. Each marble has one out of M different colours. The governess needs to divide all the marbles between the N children in her group. It is acceptable if some children don't get any marbles. However, no child wants marbles of different colours - in other words, all marbles that a child gets need to be the same colour.

The governess also knows that children will be jealous if a child gets too many marbles. As an approximation, we will define the envy level in the group as the largest number of marbles given to one child. Help the governess divide the marbles in order to minimize the envy level.

For example, if the box contains 4 red marbles (RRRR) and 7 blue marbles (BBBBBBB) which we have to divide between 5 children, we can achieve an envy level of 3 by dividing the marbles in the following way: RR, RR, BB, BB, BBB. This is the lowest achievable envy level.

입력

The first line of input contains two positive integers, N (1 ≤ N ≤ 10^9), the number of children, and M (1 ≤ M ≤ 300 000, M ≤ N), the number of different colours.

Each of the following M lines contains a positive integer from the interval [1, 10^9 ], with the integer in line K denoting the number of marbles with colour K.

출력

The first and only line of output should contain the minimum possible envy level.

입출력 예

input

5 2
7
4

output

3

input

7 5
7
1
7
4
4

output

4

출처:coci/2012-2013/contest1 4/6
[질/답] [제출 현황] [푼 후(2)]
[ 채 점 ] [홈으로]  [뒤 로]