Problem Description

There are $ N $ decks of cards, each consisting of $ M $ cards numbered from $ 1 $ to $ M $. The $ j $-th card from the top in the $ i $-th deck has the number $a_{i,\ j}$ written on it.

You can perform the following two types of operations on these decks in any order and as many times as you like:

• Operation $ 1 $: Choose one deck and move the top card to the bottom of the same deck.
• Operation $ 2 $: If the top cards of all $ N $ decks have the same number, remove them all.

What is the minimum number of times you need to perform Operation $ 1 $ to eat all the cards?

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $a_{1,\ 1}$ $\ldots$ $a_{1,\ M}$ $\vdots$ $a_{N,\ 1}$ $\ldots$ $a_{N,\ M}$

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

4 3
2 3 1
1 2 3
2 1 3
3 2 1

Sample Output #1

4

Sample Input #2

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

Sample Output #2

35

Notes/Hints

Constraints

• All inputs are integers.
• $1 \le N \le 2 \times 10^5$
• $1 \le M \le 22$
• $1 \leq a_{i,\ j} \leq M$
• $a_{i,\ j} \neq a_{i,\ k}$ $(j \neq k)$

Partial Points

• If you solve the dataset where $1 \le M \le 16$, you will be awarded $ 30 $ points.

Sample Explanation 1

You can perform the operations as follows:
- Perform Operation $ 1 $ on deck $ 2 $.
- Perform Operation $ 1 $ on deck $ 4 $.
- Perform Operation $ 2 $. (The top cards of all decks are $ 2 $.)
- Perform Operation $ 1 $ on deck $ 1 $.
- Perform Operation $ 1 $ on deck $ 2 $.
- Perform Operation $ 2 $. (The top cards of all decks are $ 1 $.)
- Perform Operation $ 2 $. (The top cards of all decks are $ 3 $.)

见题面 Input 部分

见题面 Output 部分