P17047 [NWERC 2021] 挑袜子 / Knitpicking

译自 [Northwestern Europe Regional Contest (NWERC) 2021](http://2021.nwerc.eu) 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`。

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