Andrewid the Android is a galaxy-famous detective. He is now investigating the case of vandalism at the exhibition of contemporary art.

The main exhibit is a construction of n matryoshka dolls that can be nested one into another. The matryoshka dolls are numbered from 1 to n. A matryoshka with a smaller number can be nested in a matryoshka with a higher number, two matryoshkas can not be directly nested in the same doll, but there may be chain nestings, for example, 1 → 2 → 4 → 5. 

In one second, you can perform one of the two following operations:  Having a matryoshka a that isn't nested in any other matryoshka and a matryoshka b, such that b doesn't contain any other matryoshka and is not nested in any other matryoshka, you may put a in b;  Having a matryoshka a directly contained in matryoshka b, such that b is not nested in any other matryoshka, you may get a out of b. 

According to the modern aesthetic norms the matryoshka dolls on display were assembled in a specific configuration, i.e. as several separate chains of nested matryoshkas, but the criminal, following the mysterious plan, took out all the dolls and assembled them into a single large chain (1 → 2 → ... → n). In order to continue the investigation Andrewid needs to know in what minimum time it is possible to perform this action.


-----Input-----

The first line contains integers n (1 ≤ n ≤ 10^5) and k (1 ≤ k ≤ 10^5) — the number of matryoshkas and matryoshka chains in the initial configuration.

The next k lines contain the descriptions of the chains: the i-th line first contains number m_{i} (1 ≤ m_{i} ≤ n), and then m_{i} numbers a_{i}1, a_{i}2, ..., a_{im}_{i} — the numbers of matryoshkas in the chain (matryoshka a_{i}1 is nested into matryoshka a_{i}2, that is nested into matryoshka a_{i}3, and so on till the matryoshka a_{im}_{i} that isn't nested into any other matryoshka).

It is guaranteed that m_1 + m_2 + ... + m_{k} = n, the numbers of matryoshkas in all the chains are distinct, in each chain the numbers of matryoshkas follow in the ascending order.


-----Output-----

In the single line print the minimum number of seconds needed to assemble one large chain from the initial configuration.


-----Examples-----
Input
3 2
2 1 2
1 3

Output
1

Input
7 3
3 1 3 7
2 2 5
2 4 6

Output
10



-----Note-----

In the first sample test there are two chains: 1 → 2 and 3. In one second you can nest the first chain into the second one and get 1 → 2 → 3.

In the second sample test you need to disassemble all the three chains into individual matryoshkas in 2 + 1 + 1 = 4 seconds and then assemble one big chain in 6 seconds.

Difficulty: competition

Starter code:

Solutions:
n, k = [int(c) for c in input().split()]
a = []
for i in range(k):
    ak = [int(c) for c in input().split()]
    a.append(ak[1:])

total = k - 1

for ak in a:
    if ak[0] == 1:
        j = 1
        while j <= len(ak) - 1:
            if ak[j] != ak[j-1] + 1:
                break
            j += 1
        total += 2*(len(ak) - j)
    else:
        total += 2*(len(ak) - 1)

print(total)

def read_data():
    n, k = map(int, input().split())
    As = []
    m = 0
    for i in range(k):
        ma = list(map(int, input().split()))
        As.append(ma[1:])
        m += ma[0] - 1
    return n, k, As, m

def solve(n, k, As, m):
    As.sort()
    steps = n + 1 + m
    mat1 = As[0]
    for i, mi in enumerate(mat1, 1):
        if i == mi:
            steps -= 2
        else:
            break
    return steps

n, k, As, m = read_data()
print(solve(n, k, As, m))

import sys

n, k = list(map(int, sys.stdin.readline().split()))
ans, pref = 0, 0
for i in range(k):
    m, *a = list(map(int, sys.stdin.readline().split()))
    j = 0
    while j < m and a[j] == j + 1:
        j += 1
    if j:
        pref = j
        ans += m - j
    else:
        ans += m - 1
print(ans + n - pref)


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

(N,K) = list(map(int,input().split()))

ret = 0
for k in range(K):
    nums = list(map(int,input().split()))[1:]

    group = len(nums)
    if nums[0] == 1:
        for j in range(len(nums)-1):
            if nums[j] + 1 == nums[j+1]:
                group -= 1
            else:
                break
    ret += group - 1   # split
ret += K + ret - 1   # join
print(ret)

    
        


d = input().split()

n = int(d[0])
m = int(d[1])

r = 0
q = 0

for i in range(m):
    s = [int(x) for x in input().split()][1::]
    if s[0] != 1:
        r += len(s) - 1
        q += len(s)
    else:
        if len(s) <= 1:
            q += 1
        else:
            w = 0
            while w+1 < len(s) and s[w] == s[w+1] - 1:
                w += 1
            q += len(s) - w
            r += len(s) - w - 1

print(r + q - 1)

3
n1 = []
n1 = input("").split(" ")
n = int (n1[0])
k= int(n1[1])
x= int (0)
y= int(-1)
z = int (0)


breakc = int(0)
addc = int(0)
x = []
f =int(0)
for i in range(0,k):
	x=input("").split(" ")
	y = -1
	if f != 1:
		for j in range(1,int(x[0])+1):
			z=int(x[j])
			if z==1:
				y = 1
				for k in range(j+1, int(x[0])+1):
					z=int(x[k])
					if z == (y+1):
						addc +=1
						y =z
					else:
						f = 1
					if k == int(x[0]):
						f = 1
					if f == 1:
						x[0] = int(x[0]) - addc
						
						break
			
				
					
	breakc += int(x[0]) - 1


print(breakc + (n - addc) - 1)


n, k = list(map(int, input().split()))
time = 0

ntd  = 0

for i in range(k):
	mtr = list(map(int, input().split()))[1:]

	if mtr[0] == 1:
		ln = 0

		dlt = mtr[-1]
		mtr.reverse()


		for j, val in enumerate(mtr[:-1]):
			if val-mtr[j+1] != 1:
				#print('*')
				time += j-ln+1
				#print('!', j-ln+1)
				ln = j + 1
				dlt = mtr[j+1]
				

	else:
		#print('-', i, len(mtr)-1)
		time += len(mtr)-1

#print('\n------------------\n', time, n,  dlt)
print(time + n  - dlt)


##row, col, order = input().split(' ')    
##row = int(row)
##col = int(col)
##
##init_list = []
##
##for i in range(row):
##    init_list.append(input().split(' '))
##
##if order=='0':
##    for i in range(row):
##        print()
##        for j in range(col,0,-1):
##            print(init_list[i][j-1], end = ' ')
##else:
##    for i in range(row,0,-1):
##        print()
##        for j in range(col):
##            print(init_list[i-1][j], end = ' ')

def judge(_list:list) -> int:
    number = -1
    for i in range(len(_list)):
        if int(_list[i]) == i+1:
            number += 1
        else:
            pass
    
    return number

mat_num, chain_num = input().split(' ')
mat_num, chain_num = int(mat_num), int(chain_num)

chain = []

for i in range(chain_num):
    chain.append([])
    temp_list = input().split(' ')
    for j in range(int(temp_list[0])):
        chain[-1].append(temp_list[1])
        del temp_list[1]

for i in range(chain_num):
    if judge(chain[i]) < 1:
        pass
    else:
        temp_count = len(chain[i]) - judge(chain[i])
        chain[i] = []
        for j in range(temp_count):
            chain[i].append(1)

time = 0
count = 0

for i in range(chain_num):
    time += len(chain[i]) - 1
    count += len(chain[i])

print(time + count -1)


n, k = list(map(int, input().split()))
m = [0]*k; f = 0;
for y in range(k):
    m = list(map(int, input().split()))[1:]
    i = 0
    while i < len(m):
        if m[i] == 1:
            if i > 0:
                f += 1
            j = i+1
            while j < len(m):
                if m[j] - m[j-1] != 1:
                    f += 1
                    break
                j += 1
            i = j
        elif i > 0:
            f += 1
        i += 1
print(2*f+k-1)


n, k = list(map(int, input().split(' ')))
for i in range(k):
    x = input().split(' ')
    if x[1] == '1':
        y = [int(j) for j in x[1:]] + [0]
        z = 0
        while y[z+1] == z+2:
            z += 1
print(2*n-k-1-2*z)


n, k = map(int, input().split())
for _ in range(k):
    a = list(map(int, input().split()))[1:] + [0]
    if a[0] != 1: continue
    i = 0
    while a[i + 1] == i + 2:
        i += 1
print(2 * n - k - 1 - 2 * i)

#!/usr/bin/env python3
n, k = list(map(int,input().split()))
y = 0
for i in range(k):
    xs = list(map(int,input().split()))
    m, xs = xs[0], xs[1:]
    if xs[0] == 1:
        j = 0
        while j < m and xs[j] == j+1:
            j += 1
        m -= j
        y += m # decompose
        y += m # compose
    else:
        y += m - 1 # decompose
        y += m # compose
print(y)


def main():
    n, k = list(map(int, input().split()))
    res = 0
    for _ in range(k):
        tmp = list(map(int, input().split()))
        if tmp[1] == 1:
            tmp[0] = 0
            for i, x in enumerate(tmp):
                if i != x:
                    res += (len(tmp) - i) * 2
                    break
        else:
            res += len(tmp) * 2 - 3
    print(res)


def __starting_point():
    main()

__starting_point()

def main():
    n, k = list(map(int, input().split()))
    for i in range(k):
        tmp = input().split()
        if tmp[1] == '1':
            tmp.append('0')
            tmp[0] = '0'
            for i, m in enumerate(map(int, tmp)):
                if i != m:
                    print((n - i) * 2 - k + 3)
                    return


def __starting_point():
    main()

__starting_point()

n, k = (int(x) for x in input().split())
l = [None for _ in range(k)]
for i in range(k):
	l[i] = [int(x) for x in input().split()[1:]]
for m in l:
	if m[0] == 1:
		i = 0
		while i < len(m) and m[i] == i + 1:
			i += 1
		print(n * 2 - i * 2 - k + 1)


n, k = list(map(int, input().split()))
u = 0
for i in range(k):
    a = list(map(int, input().split()))[1:]+[0]
    if a[0] == 1:
        while a[u] == u+1: u += 1
print(n+n-u-u-k+1)
            


def func(mas, n, m):
    flag1=0
    flag2=n-1
    i=0
    j=1
    while(i<m):
        if(mas[i][1]==1):
            tmp = mas[i][0]-1
            while(j<mas[i][0]):
                if(mas[i][j]==mas[i][j+1]-1):
                    flag2-=1
                    tmp-=1
                else:
                    break
                j+=1
            flag1+=tmp
        else:
            flag1=flag1+mas[i][0]-1
        i+=1
    return flag1+flag2
n,m = map(int, input().split())
mas=[[]for i in range(m)]
h=0
for i in mas:
    s = input()
    p = s.split()
    while h<len(p):
        i.append(int(p[h]))
        h+=1
    h=0
print(func(mas,n,m))

n, k = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(k)]

for row in m:
    if row[1] == 1:
        for idx in range(1, row[0] + 1):
            if row[idx] != idx:
                idx -= 1
                break
        break
ans = (n-1) + (n-k) - 2*(idx-1)
print(ans)

#!/usr/bin/env python3

def solve(n, seq):
    found = 0
    res = 0
    for s in seq:
        if s[1] == 1:
            found = 1
            while len(s) > found and s[found] == found:
                found += 1
            found -= 1
            rest = s[0] - found
            res += rest
        else:
            res += s[0]-1
    return res + n - found


def __starting_point():
    n, k = list(map(int, input().split()))
    seq = [list(map(int, input().split())) for _ in range(k)]
    print(solve(n, seq))

__starting_point()

n, k = list(map(int, input().split()))
for _ in range(k):
    a = list(map(int, input().split()))[1:] + [0]
    if a[0] != 1:
        continue
    i = 0
    while a[i + 1] == i + 2:
        i += 1
print(2 * n - k - 1 - 2 * i)


I=lambda:map(int,input().split())
n,k=I()
r=k-1
y=0
for _ in range(k):
    t=list(I())
    for i in range(1,t[0]):
        if t[i]==y+1:
            y+=1
            if t[i+1]!=t[i]+1:r+=2
        else:
            if y:y=-1
            r+=2
print(r)

# 555A
# θ(n) time
# O(n) space

__author__ = 'artyom'


# SOLUTION

def main():
    n, k = read(3)
    c = 0
    l = 1
    for _ in range(k):
        a = read(3)
        if a[1] == 1:
            j = 1
            while j < a[0] and a[j + 1] - a[j] == 1:
                j += 1
                l += 1
            c += a[0] - j
        else:
            c += a[0] - 1
    return c + n - l


# HELPERS

def read(mode=1, size=None):
    # 0: String
    # 1: Integer
    # 2: List of strings
    # 3: List of integers
    # 4: Matrix of integers
    if mode == 0: return input().strip()
    if mode == 1: return int(input().strip())
    if mode == 2: return input().strip().split()
    if mode == 3: return list(map(int, input().strip().split()))
    a = []
    for _ in range(size):
        a.append(read(3))
    return a


def write(s="\n"):
    if s is None: s = ''
    if isinstance(s, tuple) or isinstance(s, list): s = ' '.join(map(str, s))
    s = str(s)
    print(s, end="\n")


write(main())

# 555A
# O(n + k) time
# O(n) space

__author__ = 'artyom'


# SOLUTION

def main():
    n, k = read(3)
    c = 0
    l = 1
    for _ in range(k):
        a = read(3)
        if a[1] == 1:
            while l < a[0] and a[l + 1] - a[l] == 1:
                l += 1
            c += a[0] - l
        else:
            c += a[0] - 1
    return c + n - l


# HELPERS

def read(mode=1, size=None):
    # 0: String
    # 1: Integer
    # 2: List of strings
    # 3: List of integers
    # 4: Matrix of integers
    if mode == 0: return input().strip()
    if mode == 1: return int(input().strip())
    if mode == 2: return input().strip().split()
    if mode == 3: return list(map(int, input().strip().split()))
    a = []
    for _ in range(size):
        a.append(read(3))
    return a


def write(s="\n"):
    if s is None: s = ''
    if isinstance(s, tuple) or isinstance(s, list): s = ' '.join(map(str, s))
    s = str(s)
    print(s, end="\n")


write(main())

# Description of the problem can be found at http://codeforces.com/problemset/problem/555/A

n, k = map(int, input().split())

a =  2 * n - k + 1

for _ in range(k):
    x = list(map(int, input().split()))[1:]
    for i in range(len(x)):
        if i + 1 == x[i]:
            a -= 2
            
print(a)