조각 모음

새로운 운영체제의 파일 시스템을 개발하고 있다. 디스크 공간은 크기가 같은 $N$개의 클러스터로 나뉘며, 각 클러스터에는 $1$부터 $N$까지의 번호가 매겨져 있다. 각 파일은 디스크의 임의의 위치에 있는 하나 이상의 클러스터를 차지한다. 어떤 파일도 차지하지 않은 클러스터는 비어 있는 것으로 본다.

파일의 모든 클러스터가 자연스러운 순서대로 연속된 클러스터에 놓여 있을 때 그 파일을 가장 빠르게 읽을 수 있다. 디스크는 일정한 속도로 회전하므로 앞쪽 클러스터를 뒤쪽 클러스터보다 빠르게 읽을 수 있고, 따라서 접근 빈도가 높은 순서대로 파일에 $1$부터 $K$까지 번호를 매긴다. 최적 배치에서 파일 $1$은 클러스터 $1, 2, \dots, S_1$을, 파일 $2$는 클러스터 $S_1+1, \dots, S_1+S_2$를 차지하며, 이런 식으로 계속된다. 여기서 $S_i$는 파일 $i$가 차지하는 클러스터 수이다.

최적 배치에 도달하기 위해 클러스터 이동 연산을 수행한다. 한 번의 이동 연산은 어떤 사용 중인 클러스터의 내용을 읽어 비어 있는 클러스터에 쓰는 것이다. 그 후 원본 클러스터는 비게 되고 대상 클러스터는 사용 중이 된다.

모든 파일을 최적 배치로 만들기 위해 필요한 클러스터 이동 연산의 최소 횟수를 구하라.

첫 번째 줄에는 공백으로 구분된 두 정수 $N$과 $K$가 주어진다 ($1 \le K < N \le 10000$). 이어지는 $K$개의 줄은 각각 하나의 파일을 설명한다. $i$번째 파일의 설명은 파일 $i$의 클러스터 수 $S_i$ ($1 \le S_i < N$)로 시작하고, 그 뒤에 그 파일이 차지하는 클러스터 번호가 자연스러운 순서대로 $S_i$개 주어진다.

입력에 등장하는 모든 클러스터 번호는 서로 다르며, 비어 있는 클러스터는 항상 최소 하나 존재한다.

모든 파일을 최적 배치로 만들기 위해 필요한 클러스터 이동 연산의 최소 횟수를 정수 하나로 출력한다. 이미 최적 배치라면 $0$을 출력한다.