급식 배식

$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$을 넘지 않는다.

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