410603: GYM104064 K Knitpicking

K. Knitpickingtime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

ExamplesInput

3
fuzzy any 10
wool left 6
wool right 4

Output

8

Input

3
sports any 1
black left 6
white right 6

Output

impossible

Input

2
warm any 5
warm left 3

Output

4