급식 배식

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

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