일본식 퍼즐

동양에서 완전히 새로운 퍼즐이 등장하여, 세계적으로 유명한 스도쿠에 도전하고 국제적인 인기를 얻으려 하고 있다. 정확한 규칙은 아직 비밀이지만, 목표는 이미 공개되었다. $n \times n$ 크기의 정사각형 격자가 주어지며, 각 칸에는 $k$가지 그림 중 하나가 그려진 블록이 놓여 있다. 플레이어는 블록을 재배치하여 서로 같아지는 행의 수를 최대한 많게 만들어야 한다. 두 행은 같은 그림이 같은 순서로 놓여 있을 때 서로 같다고 본다.

재배치는 이미 있는 블록을 옮기기만 할 뿐, 그림 전체의 모음은 변하지 않는다. 즉, 어떤 그림도 새로 추가되거나 제거되지 않는다.

앤디는 퍼즐 리뷰 잡지에서 일하며 이 소식에 흥미를 느꼈다. 그는 지금까지 알려진 정보만으로도 최적의 배치에서 서로 같게 만들 수 있는 행의 수를 알아낼 수 있다는 것을 깨달았고, 임의의 초기 배치에 대해 이 수를 계산하는 프로그램을 작성하려 한다.

예를 들어, 다음과 같이 시작하는 퍼즐이

여러 개의 위쪽 행이 반복되도록 아래처럼 재배치될 수 있다.

첫째 줄에 두 정수 $n$과 $k$가 주어진다 ($1 \le n \le 40000$, $1 \le k \le 50000$). 다음 $k$개의 줄에는 각각 하나의 정수 $l_i$가 주어지며 ($l_i > 0$), 이는 $i$번째 종류의 그림이 그려진 블록의 개수이다. $\sum_{i=1}^{k} l_i = n^2$임이 보장된다.

서로 같게 만들 수 있는 행의 최대 개수를 정수 하나로 출력한다.