{"raw_statement":[{"iden":"statement","content":"Natasha is planning an expedition to Mars for $n$ people. One of the important tasks is to provide food for each participant.\n\nThe warehouse has $m$ daily food packages. Each package has some food type $a_i$.\n\nEach participant must eat exactly one food package each day. Due to extreme loads, each participant must eat the same food type throughout the expedition. Different participants may eat different (or the same) types of food.\n\nFormally, for each participant $j$ Natasha should select his food type $b_j$ and each day $j$\\-th participant will eat one food package of type $b_j$. The values $b_j$ for different participants may be different.\n\nWhat is the maximum possible number of days the expedition can last, following the requirements above?"},{"iden":"input","content":"The first line contains two integers $n$ and $m$ ($1 \\le n \\le 100$, $1 \\le m \\le 100$) — the number of the expedition participants and the number of the daily food packages available.\n\nThe second line contains sequence of integers $a_1, a_2, \\dots, a_m$ ($1 \\le a_i \\le 100$), where $a_i$ is the type of $i$\\-th food package."},{"iden":"output","content":"Print the single integer — the number of days the expedition can last. If it is not possible to plan the expedition for even one day, print _0_."},{"iden":"examples","content":"Input\n\n4 10\n1 5 2 1 1 1 2 5 7 2\n\nOutput\n\n2\n\nInput\n\n100 1\n1\n\nOutput\n\n0\n\nInput\n\n2 5\n5 4 3 2 1\n\nOutput\n\n1\n\nInput\n\n3 9\n42 42 42 42 42 42 42 42 42\n\nOutput\n\n3"},{"iden":"note","content":"In the first example, Natasha can assign type $1$ food to the first participant, the same type $1$ to the second, type $5$ to the third and type $2$ to the fourth. In this case, the expedition can last for $2$ days, since each participant can get two food packages of his food type (there will be used $4$ packages of type $1$, two packages of type $2$ and two packages of type $5$).\n\nIn the second example, there are $100$ participants and only $1$ food package. In this case, the expedition can't last even $1$ day."}],"translated_statement":[{"iden":"statement","content":"娜塔莎计划组织一次由 $n$ 人参与的火星远征。其中一项重要任务是为每位参与者提供食物。\n\n仓库中有 $m$ 份每日食物包裹，每份包裹具有某种食物类型 $a_i$。\n\n每位参与者每天必须食用恰好一份食物包裹。由于任务负荷极大，每位参与者在整个远征期间必须食用同一种类型的食物。不同参与者可以食用不同（或相同）类型的食物。\n\n形式化地，对于每位参与者 $j$，娜塔莎需为其选择一种食物类型 $b_j$，使得第 $j$ 位参与者每天食用一份类型为 $b_j$ 的食物包裹。不同参与者的 $b_j$ 值可以不同。\n\n在满足上述要求的前提下，此次远征最多能持续多少天？\n\n第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n lt.eq 100$，$1 lt.eq m lt.eq 100$）——分别为远征参与者人数和每日可用的食物包裹数量。\n\n第二行包含一个整数序列 $a_1, a_2, dots.h, a_m$（$1 lt.eq a_i lt.eq 100$），其中 $a_i$ 表示第 $i$ 个食物包裹的类型。\n\n请输出一个整数——远征能持续的天数。如果无法支持哪怕一天的远征，请输出 _0_。\n\n在第一个例子中，娜塔莎可以为第一位参与者分配类型 $1$ 的食物，第二位参与者也分配类型 $1$，第三位分配类型 $5$，第四位分配类型 $2$。在这种情况下，远征可以持续 $2$ 天，因为每位参与者都能获得两份其对应类型的食物包裹（共使用 $4$ 份类型 $1$、$2$ 份类型 $2$ 和 $2$ 份类型 $5$ 的包裹）。\n\n在第二个例子中，有 $100$ 名参与者，但仅有 $1$ 份食物包裹。此时，远征甚至无法持续一天。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n lt.eq 100$，$1 lt.eq m lt.eq 100$）——分别为远征参与者人数和每日可用的食物包裹数量。第二行包含一个整数序列 $a_1, a_2, dots.h, a_m$（$1 lt.eq a_i lt.eq 100$），其中 $a_i$ 表示第 $i$ 个食物包裹的类型。"},{"iden":"output","content":"请输出一个整数——远征能持续的天数。如果无法支持哪怕一天的远征，请输出 _0_。"},{"iden":"examples","content":"输入\n4 10\n1 5 2 1 1 1 2 5 7 2\n输出\n2\n\n输入\n100 1\n1\n输出\n0\n\n输入\n2 5\n5 4 3 2 1\n输出\n1\n\n输入\n3 9\n42 42 42 42 42 42 42 42 42\n输出\n3"},{"iden":"note","content":"在第一个例子中，娜塔莎可以为第一位参与者分配类型 $1$ 的食物，第二位参与者也分配类型 $1$，第三位分配类型 $5$，第四位分配类型 $2$。在这种情况下，远征可以持续 $2$ 天，因为每位参与者都能获得两份其对应类型的食物包裹（共使用 $4$ 份类型 $1$、$2$ 份类型 $2$ 和 $2$ 份类型 $5$ 的包裹）。在第二个例子中，有 $100$ 名参与者，但仅有 $1$ 份食物包裹。此时，远征甚至无法持续一天。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of participants.  \nLet $ m \\in \\mathbb{Z}^+ $ be the number of food packages.  \nLet $ A = (a_1, a_2, \\dots, a_m) $ be a sequence of food package types, where $ a_i \\in \\mathbb{Z}^+ $.  \n\nLet $ f: \\mathbb{Z}^+ \\to \\mathbb{Z}^+ $ be the frequency function over food types, i.e., for each food type $ t $, $ f(t) $ is the number of packages of type $ t $ in $ A $.\n\n**Constraints**  \n1. $ 1 \\le n \\le 100 $  \n2. $ 1 \\le m \\le 100 $  \n3. $ 1 \\le a_i \\le 100 $ for all $ i \\in \\{1, \\dots, m\\} $\n\n**Objective**  \nFind the maximum integer $ d \\in \\mathbb{Z}^{\\ge 0} $ such that there exists an assignment of food types $ b_1, b_2, \\dots, b_n \\in \\mathbb{Z}^+ $ to the $ n $ participants satisfying:  \n$$\n\\sum_{j=1}^{n} \\mathbf{1}_{b_j = t} \\le \\left\\lfloor \\frac{f(t)}{d} \\right\\rfloor \\quad \\forall t \\in \\text{range}(A)\n$$  \nEquivalently, $ d $ is the largest integer for which the multiset of frequencies $ \\{f(t)\\} $ can be partitioned into $ n $ groups (one per participant), each group assigned a single food type $ t $, and each group contains at least $ d $ packages of that type.\n\nThat is:  \n$$\n\\max \\left\\{ d \\in \\mathbb{Z}^{\\ge 0} \\ \\middle| \\ \\sum_{t} \\left\\lfloor \\frac{f(t)}{d} \\right\\rfloor \\ge n \\right\\}\n$$","simple_statement":null,"has_page_source":false}