과자 나눠주기

면접 대비

시간 제한1초메모리 제한256 MB

요약

간식 막대를 자르지 이어 붙일 수 없을 때 아이 M명에게 모두 같은 길이의 막대를 나눠 주는 최대 길이를 구합니다.

문제

명절이 되면 홍익이네 집에 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래려고 홍익이는 막대 과자를 하나씩 나눠준다.

조카들이 과자를 먹는 동안에는 떼를 쓰지 않으므로, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.

그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 모든 조카에게 반드시 같은 길이의 막대 과자를 나눠주어야 한다.

조카가 M명이고 과자가 N개 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.

막대 과자는 길이와 상관없이 여러 조각으로 나눌 수 있지만, 여러 조각을 하나로 합칠 수는 없다. 막대 과자의 길이는 양의 정수여야 한다.

첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1,000,000,000)을 만족한다.

첫째 줄에 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 출력한다.

모든 조카에게 같은 길이의 막대 과자를 나눠줄 수 없다면 0을 출력한다.