급식 배식

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 \leq 10^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} \leq 10^9$)

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

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