Japanese Puzzle

A brand-new puzzle is arriving from the East, hoping to rival the world-famous Sudoku and become an international hit. Its exact rules are still a secret, but the objective has already been announced: you are given an $n \times n$ square grid in which every cell holds a block showing one of $k$ kinds of pictures, and you must rearrange the blocks so that as many rows as possible become identical to one another. Two rows count as identical when they contain the same pictures in the same order.

Rearranging only moves the existing blocks around: the whole collection of pictures is preserved, so no picture is ever added and none is removed.

Andy works at a puzzle review magazine and became curious about the news. He realized that the information known so far is already enough to determine how many rows can be made identical in the best possible arrangement, and he wants a program that computes this number for any starting configuration.

For example, a puzzle that starts out like this

can be rearranged so that several top rows repeat, as in

The first line contains two integers $n$ and $k$ ($1 \le n \le 40000$, $1 \le k \le 50000$). Each of the next $k$ lines contains one integer $l_i$ ($l_i > 0$): the number of blocks that show the $i$-th kind of picture. It is guaranteed that $\sum_{i=1}^{k} l_i = n^2$.

Output a single integer: the maximum number of rows that can be made identical to one another.