lab of Foundations of Algorithms...C++ code

Courses Choosing

Problem Description

All university students need to register courses before the start of each semester. There are many of courses Johnson wouldl ike to take. However, there are some schedule conicts that prevent him from selecting all of them. Please write a program to help him calculate the maximum number of courses he can take.

Technical Specication

0 d 6. 0 s < t 24.

Input Format

Input consists n+1 lines. First line is an integer n that equals to the number of courses that Johnson wants to choose. The following n lines contain information about these courses. Each line consist 3 integers, d, s, and t. d equals to the day (0 is Sunday, 1 is Monday, ..., 6 is Saturday), s equals to the time the course starts (24 hours format, no leading zero, hh means begin at hh:10), t equals to the time the course ends (24 hours format, no leading zero, hh means end at hh:00).

Output Format

Single integer that equals to the maximal number of non-coliding classes.

Example

Input output

5 4

1 6 8

1 9 16

1 10 13

1 13 16

2 9 12