JinYueTuan is a famous online game which has been in vogue for a long time. Large number of players put themselves in it day after days…
JinYueTuan is a simple game with these rules:
Only seven keys on the keyboard will be used in games, each key are assigned to one of the seven sound tracks. During the game, a series of notes may fall in each sound track irregularly. When notes fall down in one sound track, player should press the assigned key at once. If so, then got a “Cool”, or get “Miss” otherwise.
There are two types of “Note”: “single note” and “strip note”. Just as the name implies, “single note” means a single note, press right key at the right time once, then you can get a “Cool”, otherwise “Miss”; “strip note” needs you keeping press the corresponding key from the start time to the end time of the note. Press key at the begin time you may get a “Cool”, and release at the end time to get another “Cool”, you will “Miss” either early or late. If “Miss” at the begin time, then “Miss” the other (the end time) immediately.
People lament about the fact that such an easy game is limited by the hardware design, the so-called “keys confliction”. “keys confliction” means some key combinations cannot be pressed. For example, when Track 1,4,5,6 fall a note at the same time respectively, we should press the four keys at the same time, but now, keys confliction may happen, and cause this to fail, then you will “Miss” all these four notes. Keys confliction meets the relation of inclusion, in other words, if keys set S would cause the confliction, so would keys set T when S is included in T. Note that, if at a certain moment in time, some keys should be pressed and some pressing keys should be released, then you can release and press at the same time, and released keys won’t cause any keys confliction at all.
Because of the keys confliction, we have to give up some notes to save as more other notes as possible. More details will be explained in the sample data.
Now you know the falling time and type (single or strip) of each note in each sound track, and all keys-assembling that may cause confliction. Your task is to calculate the maximum number of “Cool” that player can get.