시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB4871179431.333%

문제

$1$부터 $N$까지의 번호가 붙어있는 $N$개의 배식대가 있다. $i$번 배식대에서는 $i$번 음식을 배식받을 수 있다. $M$명의 학생들이 음식을 받기 위해 줄을 섰다.

각 학생은 특정 음식을 배식받을 수 있고, 배식받은 음식에 해당하는 만큼 행복도가 상승한다. 구체적인 규칙은 다음과 같다.

  • $j$번 학생은 배식받을 수 있는 음식의 번호 $p_{j,1},\,p_{j,2},\,\cdots,\,p_{j,l_j}$가 정해져 있다. 각 학생은 같은 음식을 최대 한 번만 배식받을 수 있다.
  • $j$번 학생이 $p_{j,k}$번 음식을 배식받을 경우 학생의 행복도가 $v_{j,k}$만큼 상승한다.
  • $j$번 학생이 배식받은 음식은 $j+1$번 학생이 배식받을 수 없다. $(1\leq j\leq M-1)$

초기에 모든 학생의 행복도는 $0$이다. 학생들의 행복도 합이 최대가 되도록 배식을 진행해 보자!

입력

첫 번째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. $(1\leq N,M\leq10^5)$

이후 각 학생이 먹을 수 있는 음식에 대한 정보가 $M$개의 줄에 걸쳐 주어진다.

정보의 $j$번째 줄에는 $j$번 학생이 먹을 수 있는 음식의 개수를 나타내는 정수 $l_j$가 가장 먼저 주어지고, 이후 $2l_j$개의 정수 $p_{j,1},\,v_{j,1},\,p_{j,2},\,v_{j,2},\,\cdots,\,p_{j,l_j},\,v_{j,l_j}$가 공백으로 구분되어 주어진다. 이때 $p_{j,k}$는 증가하는 순서로 주어진다. $(1\leq j\leq M;$ $1\leq l_j\leq N;$ $1\leq p_{j,1}<p_{j,2}<\cdots<p_{j,l_j}\leq N;$ $1\leq v_{j,k}\leq10^9)$

모든 $l_j$의 합은 $10^5$을 넘지 않는다.

출력

학생들의 행복도 합의 최댓값을 출력한다.

예제 입력 1

5 5
2 1 5 2 6
1 2 5
1 3 5
1 4 5
1 5 5

예제 출력 1

26

$1$번 학생이 $1$, $2$번 음식을 배식받고, $3$, $4$, $5$번 학생이 각각 $3$, $4$, $5$번 음식을 배식받으면, 학생들의 행복도의 합은 $(5 + 6) + 0 + 5 + 5 + 5 = 26$이 된다. 이 방법보다 행복도의 합을 크게 할 수 있는 방법은 없으므로, 답은 $26$이 된다.