Case of Matryoshkas

2000ms

262144K

Description:

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⁵) and k (1 ≤ k ≤ 10⁵) — 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_i1, a_i2, ..., a_{im_i} — the numbers of matryoshkas in the chain (matryoshka a_i1 is nested into matryoshka a_i2, that is nested into matryoshka a_i3, and so on till the matryoshka a_{im_i} that isn't nested into any other matryoshka).

It is guaranteed that m₁ + m₂ + ... + 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.

Sample Input:

3 2
2 1 2
1 3

Sample Output:

Sample Input:

Sample Output:

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.

Informação

Provedor Codeforces

Código CF555A