Maximum Satisfied Members

You are given N members and B books. Each member provides a ranking for the books. A member is considered satisfied if they receive one of their top three favorite books. Each book can be assigned to at most one member. Your task is to determine the maximum number of satisfied members.

Formally, let the ranking of the i^th member be a permutation of the B books. A member is satisfied if they are assigned a book that is among the top three positions of their ranking. You should assign books in such a way that the count of satisfied members is maximized. Use a greedy strategy by considering each book’s requests with their priority (0 for top preference, 1 for second, and 2 for third). Once a book is used to satisfy a member, it cannot be used for another member.

The problem can be mathematically described using the following notation:

Let \(r_{i} = [r_{i1}, r_{i2}, \dots, r_{iB}]\) be the ranking list for member \(i\). A member \(i\) is satisfied if there exists a book \(x\) assigned to them such that \(x \in \{r_{i1}, r_{i2}, r_{i3}\}\). Determine the maximum number of satisfied members.

inputFormat

The first line of input contains two integers N and B, representing the number of members and the number of books, respectively. Each of the following N lines contains B integers representing a member's ranking of the books in order of preference. It is guaranteed that each ranking is a permutation of the B books.

outputFormat

Output a single integer representing the maximum number of satisfied members, printed on a single line.

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

3