Knitpicking

Interview

Time limit1sMemory limit1024 MB

Summary

Given groups of socks with a type and a fit (left, right, any), find the minimum number of socks that must be drawn to guarantee a matching pair, or report impossible.

Level: Medium4 of 10
Topics: Greedy, Math, Implementation
Solved: No attempts yet

Problem

Kattis has many pairs of nice, warm, knit socks in her sock drawer that are perfect for the winter. These socks come in a wide range of colours and types, and have all been mixed together. Each morning Kattis needs to pick two matching socks.

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.

Examples3

Example 1

Input

3
fuzzy any 10
wool left 6
wool right 4

Expected output

Example 2

Input

3
sports any 1
black left 6
white right 6

Expected output

impossible

Example 3
Input
```
2
warm any 5
warm left 3
```
Expected output
```
4
```