0207. DVD

Input file name: dvd.in
Output file name: dvd.out
Time limit: 2 s
Memory limit: 64 megabytes

Johnie likes watching videos very much. Recently his old uncle Arnie has died and handed him down his collection of DVDs.

Johnie loved his uncle, so he must comply with his last will. Uncle Arnie was a possionate cinema adorer, so he wanted Johnie to get the full taste of XX-th century cinematograph. So he declared in his last will that Johnie must view the films he left him in chronological order. That is, if the film A was produced in year YA and the film B in year YB where YA < YB, Johnie must watch the film A before the film B. Films produced during one year may be watched in any order.

Johnie has already prepared to start watching the movie collection when a small problem has appeared: modern DVDs are protected with so called regional protection. That is, the world is divided into five parts, and each DVD can only be viewed in the region it is produced for.

Since DVD players are exported to different parts of the world, after the user buys the player, he is allowed to select the region he lives in. To correct occasional mistakes, the regional setting can be changed. However, to prevent changing region before watching each movie, the number of changes is limited to five.

Uncle Arnie loved movies so much, that he had five DVD players in his house, so he could view DVDs from all regions. However, Johnie is not so crazy about video yet, so he has only one DVD player. The collection of uncle Arnie contains many discs from various regions.

Help Johnie to select the set of films to watch and the order in which to do that. Initially his DVD player has no regional setting, so before watching the first film he must set its region. After that he can change the region for at most five times. Johnie wants to watch as many films as possible.

Input file

The first line of the input file contains n – the number of films in the collection (1 ≤ n ≤ 2000). Next n lines describe films: the name of the film in double quotes is followed by its production year and the region of the DVD. Note that uncle Arnie never had several copies of one film in his collection and no two films have the same name. Year ranges from 1870 to 2004. No film name is longer than 100 characters.

Output file

On the first line of the output file print m – the maximal number of films Johnie can watch. Next m lines must contain the names of the films in order Johnie must watch them.

Examples:

dvd.indvd.out
10 "Gone with the Wind" 1960 1 "The World and the War" 1991 5 "Back to the Future" 1980 1 "The Wall" 1980 2 "Titanic" 1997 3 "Hell on Earth" 1980 3 "Princess" 1980 4 "Yesterday" 1980 5 "Shadows of the Triumph" 1984 3 "Help" 1965 2 9 "Gone with the Wind" "Help" "The Wall" "Princess" "Yesterday" "Back to the Future" "Hell on Earth" "Shadows of the Triumph" "Titanic"


Source: Petrozavodsk Winter 2004. Andrew Stankevich Contest 4, Friday, January 30
Author: Andrew Stankevich

Discuss       Submit a solution



Printable version