디스크 최적화

디스크에는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 섹터가 있다. 블록은 번호가 연속된 섹터들의 비어 있지 않은 구간이고, 블록의 길이는 그 안에 든 섹터의 수이다. 두 블록이 공통 섹터를 갖지 않으면 서로 분리되어 있다고 한다.

디스크에는 여러 파일이 저장된다. 한 파일은 여러 섹터에 나뉘어 저장될 수 있으며, 그 섹터들이 하나의 블록을 이루지 않아도 된다. 파일의 내용은 정해진 순서대로 섹터를 읽어 이어 붙인 것이고, 각 블록 안에서는 섹터 번호가 커지는 순서로 읽는다.

파일의 배치는 (시작 섹터, 블록 길이) 쌍의 나열로 주어진다. 예를 들어 다음 나열은

7 3
2 1
5 2

파일 내용을 섹터 7, 8, 9, 그다음 2, 그다음 5, 6의 순서로 읽는다는 뜻이다.

모든 섹터는 비어 있거나, 정확히 하나의 파일의 일부를 담는다. 각 파일은 $1$부터 $P$까지의 서로 다른 정수 번호로 구분되고, $P$는 파일의 개수이다.

다음 세 조건이 모두 성립할 때 디스크가 최적화되어 있다고 한다.

• 각 파일이 하나의 블록(연속된 섹터)에 저장되어 있다,
• 번호가 작은 파일이 번호가 큰 모든 파일보다 낮은 번호의 섹터를 차지한다,
• 비어 있는 모든 섹터의 번호가 사용 중인 모든 섹터의 번호보다 크다.

다음 두 연산을 사용할 수 있다.

• 복사: 한 블록의 내용을 같은 길이의 분리된 블록으로 복사한다. 길이가 $t$인 블록을 복사하는 데 $t$마이크로초가 걸린다,
• 교환: 같은 길이의 분리된 두 블록의 내용을 서로 바꾼다. 길이가 $t$인 두 블록을 교환하는 데 $2t$마이크로초가 걸린다.

처음 배치가 주어질 때, 디스크를 최적화 상태로 만드는 데 필요한 최소 총 시간을 마이크로초 단위로 구하여라. 이미 최적화되어 있으면 답은 $0$이다.

첫 줄에 두 정수, 섹터 수 $N$ ($N \le 10000$)과 파일 수 $P$가 주어진다.

이어서 각 파일의 배치가 주어진다. 각 파일의 설명은 그 파일의 번호($1$부터 $P$까지)와 그 파일이 저장된 분리된 블록의 개수가 적힌 줄로 시작한다. 다음 줄들에는 블록이 파일의 읽는 순서대로 한 줄에 (시작 섹터, 길이) 쌍 하나씩 나열된다.

한 줄의 모든 수는 공백 하나로 구분되고, 입력은 항상 올바른 형식으로 주어진다.

디스크를 최적화하는 데 필요한 최소 총 시간을 마이크로초 단위의 정수 하나로 출력한다(이미 최적화되어 있으면 $0$을 출력한다).