背景

译自 Northwestern Europe Regional Contest (NWERC) 2021 Problem K。

原题许可协议为 CC BY-SA。

题目描述

Kattis 的袜子抽屉里有许多双漂亮、暖和、适合冬天穿的针织袜。这些袜子有各种颜色和类型，并且全部混在了一起。每天早晨，Kattis 都需要挑出两只相配的袜子。

为了找到相配的袜子，她只是不断从抽屉里随机拿出单只袜子，直到拿到一双相配的袜子为止。这可能会花很长时间，例如当她一直抽到右脚袜，却没有抽到匹配的左脚袜时。她需要一直抽多少只袜子，才能保证拿到一双可以穿的袜子？

输入格式

输入包含：

• 一行一个整数 $n$（$1 \leq n \leq 1\,000$），表示相同袜子组的数量。
• 接下来 $n$ 行，每行描述一组相同的袜子，包含以下内容：
  • 一个字符串 $i$，表示这一组袜子的类型。类型 $i$ 由 $1$ 到 $20$ 个小写英文字母组成。类型相同的袜子在穿搭意义上被认为是相配的。
  • 一个字符串 $j$，表示这一组袜子的适配脚型，取值为 left、right 或 any，分别表示适合左脚、适合右脚或左右脚都适合。
  • 一个整数 $k$（$1 \leq k \leq 1\,000$），表示抽屉中该类型且该适配脚型的袜子数量。

对于给定的一种袜子类型和一种适配脚型，在输入中最多出现一次。

输出格式

输出 Kattis 为了保证拿到一双相配袜子而至少需要抽出的袜子数量。如果根本不可能拿到相配的一双袜子，输出 impossible。

3
fuzzy any 10
wool left 6
wool right 4

8

3
sports any 1
black left 6
white right 6

impossible

2
warm any 5
warm left 3

4

提示

【数据规模与约定】

对于所有数据，$1 \leq n \leq 1\,000$；类型字符串长度在 $1$ 到 $20$ 之间，只包含小写英文字母；适配脚型为 left、right 或 any；$1 \leq k \leq 1\,000$；同一类型同一适配脚型最多出现一次。