题目描述

你正沿着一条漫长而笔直的道路行驶，目的地名称为 destination。行驶一段时间后，你忘记了自己已经走了多远，甚至可能已经在没有注意到的情况下驶过了目的地。

你的朋友记得沿途经过的每一块路牌以及它们出现的先后顺序。你们决定继续行驶到下一块路牌，并尝试根据这些信息确定当前位置到目的地的距离。不过，你只会在朋友记忆的全部信息彼此一致时相信他。

每块路牌上的信息是若干个用分号 ; 分隔的项目，每个项目由一个地点名称和一个非负整数距离组成，中间以一个空格分隔。例如，第 $i$ 块路牌写着：

A 10;B 15

若这块路牌在道路坐标 $S_i$ 处，则地点 A 位于 $S_i+10$，地点 B 位于 $S_i+15$。地点和路牌的位置可以不是整数，不同地点允许位于同一位置，地点也允许与路牌位于同一位置。

朋友声称路牌顺序也没有记错，因此所有路牌的位置必须满足 $S_0<S_1<\cdots<S_{n-1}$，任意两块路牌不能位于同一位置。你目前正位于最后一块路牌的位置 $S_{n-1}$。

如果存在一种地点与路牌的位置安排，使所有信息及路牌顺序均成立，并且能够唯一确定当前位置到 destination 的非负距离，则输出该距离。以下任意一种情况均输出 -1：

• 所有信息彼此矛盾，不存在合法的位置安排；
• 无法唯一确定当前位置到目的地的距离；
• 目的地已经位于当前位置后方，即你已经驶过目的地。

输入格式

第一行一个整数 $n$，表示路牌数量。

接下来 $n$ 行，第 $i$ 行为字符串 signs[i]，表示朋友记忆中的第 $i$ 块路牌内容。每行应作为一个完整字符串读取，其中可能包含空格和分号。

最后一行一个只包含大写英文字母的字符串 destination，表示目的地名称。

输出格式

若能够唯一确定当前位置到目的地的非负距离，输出这个整数；否则输出 -1。

样例 1

1
COLCHESTER 5;GLASTONBURY 25;MARLBOROUGH 13
GLASTONBURY

25

你正位于唯一一块路牌旁，路牌直接给出了到目的地的距离。

样例 2

2
COLCHESTER 5;GLASTONBURY 25;MARLBOROUGH 13
MARLBOROUGH 2
GLASTONBURY

14

第一块路牌说明 GLASTONBURY 比 MARLBOROUGH 更靠前 12 个单位。当前位置距离 MARLBOROUGH 为 2，因此距离 GLASTONBURY 为 14。

样例 3

2
COLCHESTER 5;GLASTONBURY 25;MARLBOROUGH 13
GLASTONBURY 13;MARLBOROUGH 2
GLASTONBURY

-1

两块路牌给出的 GLASTONBURY 与 MARLBOROUGH 的相对位置矛盾，因此即使最后一块路牌直接写出了目的地距离，也必须输出 -1。

样例 4

2
GLASTONBURY 8
GLASTONBURY 10
GLASTONBURY

-1

第二块路牌的位置必须更靠前，但它给出的目的地距离反而更大，不可能满足要求。

样例 5

2
COLCHESTER 5;GLASTONBURY 25
MARLBOROUGH 2
GLASTONBURY

-1

两块路牌之间没有任何共同地点信息，无法确定当前位置到目的地的距离。

样例 6

2
A 25;B 15
A 2
B

-1

由信息可知当前位置已经驶过 B 8 个单位，因此输出 -1。

数据范围与保证

• $1\le n\le 50$；
• 地点名称由 1 至 50 个大写英文字母组成；
• 每个距离都是 $0$ 至 $10000$ 之间的整数，且没有前导零；
• 每个 signs[i] 的长度为 1 至 50；
• 每块路牌由一个或多个以分号分隔的 地点名称 距离 项目组成；
• 同一块路牌不会重复出现同一地点；
• 所有路牌中出现的不同地点不超过 100 个；
• destination 是一个合法的地点名称，但不保证在路牌中出现；
• 输入不保证彼此一致。