{"problem":{"name":"B. Need For Brake","description":{"content":"Vasya plays the Need For Brake. He plays because he was presented with a new computer wheel for birthday! Now he is sure that he will win the first place in the championship in his favourite racing co","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF73B"},"statements":[{"statement_type":"Markdown","content":"Vasya plays the Need For Brake. He plays because he was presented with a new computer wheel for birthday! Now he is sure that he will win the first place in the championship in his favourite racing computer game!\n\n_n_ racers take part in the championship, which consists of a number of races. After each race racers are arranged from place first to _n_\\-th (no two racers share the same place) and first _m_ places are awarded. Racer gains _b__i_ points for _i_\\-th awarded place, which are added to total points, obtained by him for previous races. It is known that current summary score of racer _i_ is _a__i_ points. In the final standings of championship all the racers will be sorted in descending order of points. Racers with an equal amount of points are sorted by increasing of the name in lexicographical order.\n\nUnfortunately, the championship has come to an end, and there is only one race left. Vasya decided to find out what the highest and lowest place he can take up as a result of the championship.\n\n## Input\n\nThe first line contains number _n_ (1 ≤ _n_ ≤ 105) — number of racers. Each of the next _n_ lines contains _s__i_ and _a__i_ — nick of the racer (nonempty string, which consist of no more than 20 lowercase Latin letters) and the racer's points (0 ≤ _a__i_ ≤ 106). Racers are given in the arbitrary order.\n\nThe next line contains the number _m_ (0 ≤ _m_ ≤ _n_). Then _m_ nonnegative integer numbers _b__i_ follow. _i_\\-th number is equal to amount of points for the _i_\\-th awarded place (0 ≤ _b__i_ ≤ 106).\n\nThe last line contains Vasya's racer nick.\n\n## Output\n\nOutput two numbers — the highest and the lowest place Vasya can take up as a result of the championship.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Vasya 正在玩《Need For Brake》。他玩这款游戏是因为生日时收到了一台新的电脑方向盘！现在他确信自己将在他最爱的赛车游戏中赢得锦标赛的第一名！\n\n#cf_span[n] 名车手参加锦标赛，锦标赛由若干场比赛组成。每场比赛结束后，车手按名次从第一到第 #cf_span[n]-th 排列（没有两名车手共享同一名次），前 #cf_span[m] 名获得积分。车手在第 #cf_span[i] 名获得 #cf_span[bi] 分，这些分数将加到他此前所有比赛获得的总分中。已知车手 #cf_span[i] 当前的总分为 #cf_span[ai] 分。锦标赛最终排名将根据总分降序排列；总分相同的车手按名称的字典序升序排列。\n\n不幸的是，锦标赛只剩下最后一场比赛。Vasya 想知道，在最终排名中，他可能取得的最高名次和最低名次分别是多少。\n\n第一行包含数字 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 车手数量。接下来的 #cf_span[n] 行每行包含 #cf_span[si] 和 #cf_span[ai] —— 车手的昵称（非空字符串，由不超过 20 个小写拉丁字母组成）和该车手的当前得分 (#cf_span[0 ≤ ai ≤ 106])。车手的输入顺序是任意的。\n\n下一行包含数字 #cf_span[m] (#cf_span[0 ≤ m ≤ n])。接着是 #cf_span[m] 个非负整数 #cf_span[bi]。第 #cf_span[i] 个数表示第 #cf_span[i] 名获得的积分 (#cf_span[0 ≤ bi ≤ 106])。\n\n最后一行包含 Vasya 的车手昵称。\n\n请输出两个数字 —— Vasya 在锦标赛最终排名中可能取得的最高名次和最低名次。\n\n## Input\n\n第一行包含数字 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 车手数量。接下来的 #cf_span[n] 行每行包含 #cf_span[si] 和 #cf_span[ai] —— 车手的昵称（非空字符串，由不超过 20 个小写拉丁字母组成）和该车手的当前得分 (#cf_span[0 ≤ ai ≤ 106])。车手的输入顺序是任意的。下一行包含数字 #cf_span[m] (#cf_span[0 ≤ m ≤ n])。接着是 #cf_span[m] 个非负整数 #cf_span[bi]。第 #cf_span[i] 个数表示第 #cf_span[i] 名获得的积分 (#cf_span[0 ≤ bi ≤ 106])。最后一行包含 Vasya 的车手昵称。\n\n## Output\n\n请输出两个数字 —— Vasya 在锦标赛最终排名中可能取得的最高名次和最低名次。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of racers.  \nLet $ R = \\{ (s_i, a_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of racers, where:  \n- $ s_i \\in \\Sigma^{*} $ is the unique nickname (string of lowercase Latin letters),  \n- $ a_i \\in \\mathbb{Z}_{\\geq 0} $ is the current total score of racer $ i $.  \n\nLet $ m \\in \\mathbb{Z}_{\\geq 0} $ be the number of awarded positions in the final race.  \nLet $ B = (b_1, b_2, \\dots, b_m) \\in \\mathbb{Z}_{\\geq 0}^m $ be the point award vector, where $ b_i $ is the points awarded for the $ i $-th place in the final race.  \n\nLet $ v \\in \\Sigma^{*} $ be Vasya’s nickname. Let $ v^* \\in \\{1, \\dots, n\\} $ be the index such that $ s_{v^*} = v $.  \n\nLet $ P = \\{ p_1, p_2, \\dots, p_m \\} \\subseteq \\{1, \\dots, n\\} $ be the set of distinct racer indices assigned to the top $ m $ positions in the final race (a permutation of size $ m $).  \n\nAfter the final race, the final score of racer $ i $ is:  \n$$\na_i' = a_i + \\begin{cases} \nb_j & \\text{if racer } i \\text{ is assigned to position } j \\in \\{1, \\dots, m\\} \\text{ in the final race}, \\\\\n0 & \\text{otherwise}.\n\\end{cases}\n$$\n\nThe final ranking is determined by:  \n1. Descending order of $ a_i' $,  \n2. For equal scores: ascending lexicographical order of $ s_i $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 0 \\leq m \\leq n $  \n3. $ 0 \\leq a_i \\leq 10^6 $ for all $ i $  \n4. $ 0 \\leq b_j \\leq 10^6 $ for all $ j \\in \\{1, \\dots, m\\} $  \n5. $ |s_i| \\leq 20 $, $ s_i \\in \\text{lowercase Latin letters} $  \n6. All $ s_i $ are distinct.  \n\n**Objective**  \nDetermine:  \n- $ \\text{best} $: the highest possible rank (i.e., smallest rank number) Vasya can achieve over all possible assignments of the $ m $ awarded positions to the $ n $ racers.  \n- $ \\text{worst} $: the lowest possible rank (i.e., largest rank number) Vasya can achieve over all possible assignments of the $ m $ awarded positions to the $ n $ racers.  \n\n**Note**: The assignment of the $ m $ positions is a choice of $ m $ distinct racers to receive $ b_1, b_2, \\dots, b_m $ points respectively; the remaining $ n - m $ racers receive 0 additional points.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF73B","tags":["binary search","greedy","sortings"],"sample_group":[["3\nteama 10\nteamb 20\nteamc 40\n2\n10 20\nteama","2 3"],["2\nteama 10\nteamb 10\n2\n10 10\nteamb","2 2"]],"created_at":"2026-03-03 11:00:39"}}