← 返回题目列表

Codeforces · 73/B

B. 需要刹车

中文机器翻译题面 查看原题

Vasya 演奏《极品刹车》。他玩是因为他生日时收到了一个新的电脑轮子!现在他确信自己会在自己最喜欢的赛车电脑游戏中夺得冠军!

n 名赛车手参加锦标赛,该锦标赛由多场比赛组成。每场比赛结束后,参赛者按从第一名到第 n 名的顺序排列(没有两名参赛者共享相同的名次),并授予前 m 个名次。赛车手获得第 i 个奖励名次的 bi 积分,该积分将添加到他之前比赛中获得的总积分中。已知赛车手i当前的总得分为ai分。在最终的冠军排名中,所有参赛者将按照积分降序排列。积分相同的赛车手按照名字按字典顺序递增排序。

不幸的是,锦标赛已经结束,只剩下一场比赛了。瓦夏决定找出他在冠军赛中能获得的最高和最低名次。

输入

第一行包含数字 n (1 ≤ n ≤ 105) — 赛车手的数量。接下来的 n 行中的每一行都包含 si 和 ai — 赛车手的昵称(非空字符串,由不超过 20 个小写拉丁字母组成)和赛车手的分数 (0 ≤ ai ≤ 106)。赛车手以任意顺序给出。

下一行包含数字 m (0 ≤ m ≤ n)。接下来是 m 个非负整数 bi。第 i 个数字等于第 i 个获奖名额的分数 (0 ≤ bi ≤ 106)。

最后一行包含 Vasya 的赛车手昵称。

输出

输出两个数字——Vasya 在冠军赛中可以占据的最高位置和最低位置。

示例

输入 #1

3
teama 10
teamb 20
teamc 40
2
10 20
teama

输出 #1

2 3

输入 #2

2
teama 10
teamb 10
2
10 10
teamb

输出 #2

2 2