Problem M
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 |
.jpg){kind=link}