Hide

Problem C
Painting a Fence

You need to hire some people to paint a fence. The fence is composed of $10\, 000$ contiguous sections, numbered from $1$ to $10\, 000$.

You get some offers from painters to help paint the fence. Each painter offers to paint a contiguous subset of fence sections in a particular color. You need to accept a set of the offers, such that:

  • Each section of the fence is painted.

  • At most 3 colors are used to paint the fence.

If it is possible to satisfy these two requirements, find the minimum number of offers that you must accept.

Input

The first line of input contains an integer $N$, the number of offers. Then follow $N$ lines, one for each offer, each containing “$C$ $A$ $B$” where $C$ is the color, which is an uppercase string of up to 10 letters, $A$ is the first section and $B$ is the last section to be painted. $1 \leq A \leq B \leq 10\, 000$.

You may assume that $1 \leq N \leq 300$.

Output

Output one line containing the number of offers that need to be accepted, or “IMPOSSIBLE” if there is no acceptable set of offers.

Sample Input 1 Sample Output 1
2
BLUE 1 5000
RED 5001 10000
2
Sample Input 2 Sample Output 2
3
BLUE 1 6000
RED 2000 8000
WHITE 7000 10000
3
Sample Input 3 Sample Output 3
4
BLUE 1 3000
RED 2000 5000
ORANGE 4000 8000
GREEN 7000 10000
IMPOSSIBLE
Sample Input 4 Sample Output 4
2
BLUE 1 4000
RED 4002 10000
IMPOSSIBLE
Sample Input 5 Sample Output 5
3
BLUE 1 6000
RED 4000 10000
ORANGE 3000 8000
2

Please log in to submit a solution to this problem

Log in