Problem K
Knitpicking
To find matching socks, she simply randomly takes single socks out of the drawer until she has a matching pair. It may take a long time, for example when she keeps drawing right socks without a matching left one. How long does she need to keep drawing socks until she is guaranteed to have a pair to wear?
Input
The input consists of:

One line with an integer $n$ ($1 \leq n \leq 1\, 000$), the number of groups of identical socks.

$n$ lines, each describing a group of identical socks with the following:

A string $i$, the type of the socks in the group. The type $i$ consists of between $1$ and $20$ lowercase English letters. Socks with the same type are considered compatible for fashion purposes.

A string $j$, the fit of the socks in the group, which is either left, right or any, indicating whether the socks fit on the left foot, the right foot or any foot.

An integer $k$ ($1\leq k \leq 1\, 000$), the number of socks in the drawer that are of this type and fit.

A given fit of a given type of sock appears at most once in the input.
Output
Output the minimum number of socks Kattis needs to draw to be guaranteed to get a matching pair. If it is not possible to get a matching pair at all, output impossible.
Sample Input 1  Sample Output 1 

3 fuzzy any 10 wool left 6 wool right 4 
8 
Sample Input 2  Sample Output 2 

3 sports any 1 black left 6 white right 6 
impossible 
Sample Input 3  Sample Output 3 

2 warm any 5 warm left 3 
4 