양말 짝 맞추기

Kattis는 서랍에 겨울에 딱 좋은 따뜻한 니트 양말을 여러 켤레 가지고 있다. 이 양말들은 다양한 색과 종류로 이루어져 있고, 모두 뒤섞여 있다. Kattis는 아침마다 짝이 맞는 양말 두 짝을 골라야 한다.

짝이 맞는 양말을 찾기 위해, Kattis는 짝이 맞는 한 켤레를 얻을 때까지 서랍에서 양말을 하나씩 무작위로 꺼낸다. 왼쪽 양말 없이 오른쪽 양말만 계속 꺼내는 경우처럼 오래 걸릴 수도 있다. Kattis가 신을 수 있는 짝을 반드시 얻으려면 양말을 몇 짝이나 꺼내야 할까?

입력은 다음과 같다.

• 정수 $n$ ($1 \leq n \leq 1\,000$)이 있는 한 줄. $n$은 동일한 양말 그룹의 수이다.

• $n$개의 줄. 각 줄은 동일한 양말 그룹을 다음과 같이 설명한다.

  • 문자열 $i$는 그룹에 속한 양말의 종류이다. 종류 $i$는 1자 이상 20자 이하의 소문자 영어 알파벳으로 이루어진다. 같은 종류의 양말은 패션상 서로 어울리는 것으로 간주한다.
  • 문자열 $j$는 그룹에 속한 양말의 맞음새로, left, right, any 중 하나이며, 각각 왼발에 맞는지, 오른발에 맞는지, 어느 발에나 맞는지를 나타낸다.
  • 정수 $k$ ($1\leq k \leq 1\,000$)는 서랍에 있는 이 종류와 맞음새의 양말 수이다.

같은 종류와 같은 맞음새의 양말은 입력에 최대 한 번만 나타난다.

Kattis가 짝이 맞는 한 켤레를 반드시 얻기 위해 꺼내야 하는 최소 양말 수를 출력한다. 짝이 맞는 한 켤레를 얻는 것이 아예 불가능하면 impossible을 출력한다.