Activity Scheduling

You are given N activities and T time slots. Each activity has a unique preference list of time slots, which is a permutation of the slots from 1 to T. The task is to schedule as many activities as possible, assigning each activity to one of its preferred time slots without any conflicts. In other words, an activity can be scheduled if there exists at least one time slot (according to its preference order) that has not been assigned to a previous activity.

The objective is to maximize the number of activities scheduled. Formally, if we denote by \(scheduled[i]\) the indicator for whether time slot \(i\) is already occupied, then for each activity with preference list \(p_1, p_2, \dots, p_T\), the algorithm should assign it the first available slot \(p_j\) such that \(scheduled[p_j] = false\). The final answer is the total count of scheduled activities.

Input Format: The first line contains two integers, \(N\) and \(T\). This is followed by \(N\) lines, each containing \(T\) integers which represent the preference order for an activity.

Output Format: A single integer denoting the maximum number of activities that can be scheduled.

inputFormat

The input is read from stdin and consists of:

1. The first line contains two space-separated integers \(N\) (the number of activities) and \(T\) (the number of time slots).
2. The following \(N\) lines each contain \(T\) space-separated integers, representing the preference order of time slots for each activity.

outputFormat

Output a single integer to stdout, which is the maximum number of activities that can be scheduled without conflicts.

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

3