보석 상자

한 보석 공장이 보석 상자를 유치원에 기증했다. 각 보석은 서로 다른 M가지 색상 중 하나에 속한다. 원장 선생님은 상자 안의 모든 보석을 N명의 아이들에게 나누어 주려고 한다. 보석을 받지 못하는 아이가 있어도 되지만, 한 아이가 받는 보석은 모두 같은 색상이어야 한다.

어떤 아이가 너무 많은 보석을 받으면 다른 아이들이 질투할 수 있다. 이때 질투심은 보석을 가장 많이 받은 아이가 가진 보석의 개수로 정의한다. 원장 선생님은 이 질투심이 가능한 한 작아지도록 보석을 나누어 주려고 한다.

예를 들어 빨간 보석이 4개(RRRR), 파란 보석이 7개(BBBBBBB) 있고 아이가 5명이라면, RR, RR, BB, BB, BBB처럼 나누어 줄 수 있다. 이때 가장 많이 받은 아이는 보석 3개를 가지므로 질투심은 3이며, 이보다 작은 값으로는 모든 보석을 나누어 줄 수 없다.

상자 안의 색상별 보석 개수와 아이들의 수가 주어질 때, 가능한 질투심의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 아이들의 수 N과 색상의 수 M이 주어진다. (1 <= N <= 10^9, 1 <= M <= 300,000, M <= N)

다음 M개의 줄에는 각 색상 보석의 개수가 한 줄에 하나씩 주어진다. K번째 줄의 수는 K번 색상 보석의 개수이며, 각 값은 1 이상 10^9 이하의 정수이다.

질투심의 최솟값을 첫째 줄에 출력한다.