Description

Legendary Face Middle School is now recruiting students!

There are $n$ teachers in the school, and they need to teach $m$ subjects. Each teacher can use a triple $(a_i,b_i,c_i)$ to indicate that he teaches $a_i$, and can teach at most $b_i$ classes. If $c_i = 0$, it means that teacher $i$ is unwilling to be a class teacher, otherwise it means that he is willing to be a class teacher.

In particular, because being a class teacher will consume a lot of energy, if a teacher $i$ chooses to be a class teacher, he can only teach at most $b_i - 1$ classes.

Of course, each class must have a class teacher, and each subject must have a teacher. It should be noted that a class teacher does not necessarily have to be the subject teacher of the class he or she is assigned to.

The school hopes to form more classes to recruit more outstanding OIers. The admissions team specially invites you, as a Legendary Grandmaster, to help calculate the maximum number of classes that can be formed.

Input Format

The first line reads two positive integers $n,m$, which represent the number of teachers and the number of subjects in Legendary Face Middle School.

Next $n$, each line contains three integers $a_i,b_i,c_i$, as described in the question.

Output Format

The output is one line, indicating the maximum number of classes that can be formed in Legendary Face Middle School.

5 2
1 2 1
1 2 1
1 1 0
2 2 1
2 2 1

3

Hint

Sample Explanation

Teachers numbered $1,2,4$ are homeroom teachers for three classes, respectively.

Teachers numbered $1,2,3$ teach Subject 1 to three classes, respectively.

Teacher numbered $4$ teaches Subject 2 to one class, and teacher numbered $5$ teaches Subject 3 to two classes.

Data range

• Special property A: Satisfy $\forall i \in [1,n],c_i = 0$.
• Special property B: $\forall i \in [1,n],b_i = 1$.

For $100\%$ of the data:

• $m \leq n$.
• $\forall i \in [1,n]$, $1 \leq a_i \leq m$, $1 \leq b_i \leq n$, $c_i \in \{0,1\}$.