{"problem":{"name":"A. Heroes","description":{"content":"The year of 2012 is coming... According to an ancient choradrican legend in this very year, in 2012, Diablo and his brothers Mephisto and Baal will escape from hell, and innumerable hordes of demons ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF77A"},"statements":[{"statement_type":"Markdown","content":"The year of 2012 is coming...\n\nAccording to an ancient choradrican legend in this very year, in 2012, Diablo and his brothers Mephisto and Baal will escape from hell, and innumerable hordes of demons will enslave the human world. But seven brave heroes have already gathered on the top of a mountain Arreat to protect us mere mortals from the effect of this terrible evil.\n\nThe seven great heroes are: amazon _Anka_, barbarian _Chapay_, sorceress _Cleo_, druid _Troll_, necromancer _Dracul_, paladin _Snowy_ and a professional hit girl _Hexadecimal_. Heroes already know how much experience will be given for each of the three megabosses: _a_ for Mephisto, _b_ for Diablo and _c_ for Baal.\n\nHere's the problem: heroes are as much as seven and megabosses are only three! Then our heroes decided to split into three teams, where each team will go to destroy their own megaboss. Each team member will receive a of experience, rounded down, where _x_ will be the amount of experience for the killed megaboss and _y_ — the number of people in the team.\n\nHeroes do not want to hurt each other's feelings, so they want to split into teams so that the difference between the hero who received the maximum number of experience and the hero who received the minimum number of experience were minimal. Since there can be several divisions into teams, then you need to find the one in which the total amount of liking in teams were maximum.\n\nIt is known that some heroes like others. But if hero _p_ likes hero _q_, this does not mean that the hero _q_ likes hero _p_. No hero likes himself.\n\nThe total amount of liking in teams is the amount of ordered pairs (_p_, _q_), such that heroes _p_ and _q_ are in the same group, and hero _p_ likes hero _q_ (but it is not important if hero _q_ likes hero _p_). In case of heroes _p_ and _q_ likes each other and they are in the same group, this pair should be counted twice, as (_p_, _q_) and (_q_, _p_).\n\nA team can consist even of a single hero, but it is important that every megaboss was destroyed. All heroes must be involved in the campaign against evil. None of the heroes can be in more than one team.\n\nIt is guaranteed that every hero is able to destroy any megaboss alone.\n\n## Input\n\nThe first line contains a single non-negative integer _n_ (0 ≤ _n_ ≤ 42) — amount of liking between the heroes. Next _n_ lines describe liking in the form \"_p likes q_\", meaning that the hero _p_ likes the hero _q_ (_p_  ≠  _q_). Every liking is described in the input exactly once, no hero likes himself.\n\nIn the last line are given three integers _a_, _b_ and _c_ (1 ≤ _a_, _b_, _c_ ≤ 2·109), separated by spaces: the experience for Mephisto, the experience for Diablo and experience for Baal.\n\nIn all the pretests, except for examples from the statement, the following condition is satisfied: _a_ = _b_ = _c_.\n\n## Output\n\nPrint two integers — the minimal difference in the experience between two heroes who will receive the maximum and minimum number of experience points, and the maximal total amount of liking in teams (the number of friendships between heroes that end up in one team).\n\n**When calculating the second answer, the team division should satisfy the difference-minimizing contraint. I.e. primary you should minimize the difference in the experience and secondary you should maximize the total amount of liking.**\n\n[samples]\n\n## Note\n\n**A note to first example:** it the first team should be _Dracul_, _Troll_ and _Anka_, in the second one _Hexadecimal_ and _Snowy_, and in the third _Cleo_ и _Chapay_.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"2012年即将来临...\n\n根据古老的Choradrican传说，就在2012年，Diablo及其兄弟Mephisto和Baal将从地狱逃脱，无数恶魔军团将奴役人类世界。但七位勇敢的英雄已经聚集在Arreat山顶，保护我们这些凡人免受这可怕邪恶的影响。\n\n七位伟大英雄分别是：女战士 _Anka_、野蛮人 _Chapay_、女法师 _Cleo_、德鲁伊 _Troll_、死灵法师 _Dracul_、圣骑士 _Snowy_ 和专业刺客女孩 _Hexadecimal_。英雄们已经知道击败每个三大首领所获得的经验值：#cf_span[a] 用于 Mephisto，#cf_span[b] 用于 Diablo，#cf_span[c] 用于 Baal。\n\n问题是：英雄有七位，而三大首领只有三位！于是英雄们决定分成三支队伍，每支队伍负责消灭一个三大首领。每支队伍的每位成员将获得 $\\left\\lfloor \\frac{x}{y} \\right\\rfloor$ 的经验，其中 #cf_span[x] 是被击败的三大首领提供的经验，#cf_span[y] 是该队伍的人数。\n\n英雄们不希望伤害彼此的感情，因此他们希望将队伍划分得使得获得最多经验的英雄与获得最少经验的英雄之间的经验差值最小。由于可能存在多种分队方式，你需要找到其中 #cf_span(class=[tex-font-style-underline], body=[队伍中总喜爱值]) 最大的一种。\n\n已知某些英雄喜欢其他英雄。但如果英雄 #cf_span[p] 喜欢英雄 #cf_span[q]，并不意味着英雄 #cf_span[q] 也喜欢英雄 #cf_span[p]。没有任何英雄喜欢自己。\n\n队伍中的总喜爱值是指有序对 #cf_span[(p, q)] 的数量，满足英雄 #cf_span[p] 和 #cf_span[q] 在同一队伍中，且英雄 #cf_span[p] 喜欢英雄 #cf_span[q]（英雄 #cf_span[q] 是否喜欢英雄 #cf_span[p] 并不重要）。如果英雄 #cf_span[p] 和 #cf_span[q] 彼此喜欢且在同一队伍中，该对应被计为两次，即 #cf_span[(p, q)] 和 #cf_span[(q, p)]。\n\n一支队伍甚至可以只由一名英雄组成，但重要的是每个三大首领都必须被消灭。所有英雄都必须参与对抗邪恶的行动。没有任何英雄可以属于超过一支队伍。\n\n保证每位英雄都能单独击败任何三大首领。\n\n第一行包含一个非负整数 #cf_span[n] (#cf_span[0 ≤ n ≤ 42]) —— 英雄之间的喜爱关系数量。接下来 #cf_span[n] 行以 \"_p likes q_\" 的形式描述喜爱关系，表示英雄 _p_ 喜欢英雄 _q_（_p_ #cf_span[ ≠ ] _q_）。每条喜爱关系在输入中仅出现一次，没有任何英雄喜欢自己。\n\n最后一行给出三个整数 #cf_span[a], #cf_span[b] 和 #cf_span[c] (#cf_span[1 ≤ a, b, c ≤ 2·109])，用空格分隔：分别表示击败 Mephisto、Diablo 和 Baal 所获得的经验值。\n\n在除题目示例外的所有预测试中，均满足条件：#cf_span[a = b = c]。\n\n请输出两个整数：获得最多经验与最少经验的两位英雄之间的最小经验差值，以及在满足上述最小差值约束下，队伍中最大的总喜爱值（即最终在同一队伍中的英雄间喜爱关系总数）。\n\n*在计算第二个答案时，队伍划分必须满足最小化经验差值的约束。即首要目标是最小化经验差值，次要目标是最大化总喜爱值。*\n\n*第一组示例说明：第一支队伍应为 _Dracul_、_Troll_ 和 _Anka_，第二支为 _Hexadecimal_ 和 _Snowy_，第三支为 _Cleo_ 和 _Chapay_。*\n\n## Input\n\n第一行包含一个非负整数 #cf_span[n] (#cf_span[0 ≤ n ≤ 42]) —— 英雄之间的喜爱关系数量。接下来 #cf_span[n] 行以 \"_p likes q_\" 的形式描述喜爱关系，表示英雄 _p_ 喜欢英雄 _q_（_p_ #cf_span[ ≠ ] _q_）。每条喜爱关系在输入中仅出现一次，没有任何英雄喜欢自己。最后一行给出三个整数 #cf_span[a], #cf_span[b] 和 #cf_span[c] (#cf_span[1 ≤ a, b, c ≤ 2·109])，用空格分隔：分别表示击败 Mephisto、Diablo 和 Baal 所获得的经验值。在除题目示例外的所有预测试中，均满足条件：#cf_span[a = b = c]。\n\n## Output\n\n请输出两个整数：获得最多经验与最少经验的两位英雄之间的最小经验差值，以及在满足上述最小差值约束下，队伍中最大的总喜爱值（即最终在同一队伍中的英雄间喜爱关系总数）。*在计算第二个答案时，队伍划分必须满足最小化经验差值的约束。即首要目标是最小化经验差值，次要目标是最大化总喜爱值。*\n\n[samples]\n\n## Note\n\n*第一组示例说明：第一支队伍应为 _Dracul_、_Troll_ 和 _Anka_，第二支为 _Hexadecimal_ 和 _Snowy_，第三支为 _Cleo_ 和 _Chapay_。*","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ H = \\{h_1, h_2, \\dots, h_7\\} $ be the set of seven heroes: Anka, Chapay, Cleo, Troll, Dracul, Snowy, Hexadecimal.  \nLet $ E = (a, b, c) \\in \\mathbb{Z}_{>0}^3 $ be the experience values for Mephisto, Diablo, and Baal respectively.  \nLet $ L \\subseteq H \\times H $ be the set of directed liking relations, with $ |L| = n $, $ 0 \\leq n \\leq 42 $, and $ (p, q) \\in L \\Rightarrow p \\ne q $, and no self-loops.\n\nLet $ \\mathcal{P} $ be the set of all partitions of $ H $ into exactly three non-empty subsets $ (T_1, T_2, T_3) $, where each $ T_i \\subseteq H $, $ T_i \\ne \\emptyset $, $ T_i \\cap T_j = \\emptyset $ for $ i \\ne j $, and $ \\bigcup_{i=1}^3 T_i = H $.\n\nFor a partition $ P = (T_1, T_2, T_3) \\in \\mathcal{P} $, assign the experience values $ a, b, c $ to the three teams in all $ 3! = 6 $ possible bijections (since each team destroys one boss). For each assignment, define:\n\n- Experience per hero in team $ T_i $ assigned to boss with experience $ x \\in \\{a,b,c\\} $: $ \\left\\lfloor \\frac{x}{|T_i|} \\right\\rfloor $\n\n**Constraints**  \n1. Each team is non-empty: $ |T_i| \\geq 1 $ for $ i = 1,2,3 $  \n2. All heroes are assigned to exactly one team: $ \\sum_{i=1}^3 |T_i| = 7 $  \n3. Each boss is assigned to exactly one team: the mapping from teams to $ (a,b,c) $ is bijective  \n\n**Objective**  \nFind the partition $ P = (T_1, T_2, T_3) \\in \\mathcal{P} $ and assignment $ \\sigma: \\{T_1, T_2, T_3\\} \\to \\{a,b,c\\} $ (bijection) that:\n\n1. **Primary**: Minimizes the difference between the maximum and minimum experience per hero across all heroes:  \n   $$\n   \\Delta(P, \\sigma) = \\max_{i \\in \\{1,2,3\\}} \\left\\lfloor \\frac{\\sigma(T_i)}{|T_i|} \\right\\rfloor - \\min_{i \\in \\{1,2,3\\}} \\left\\lfloor \\frac{\\sigma(T_i)}{|T_i|} \\right\\rfloor\n   $$\n\n2. **Secondary**: Among all $ (P, \\sigma) $ achieving the minimal $ \\Delta(P, \\sigma) $, maximize the total liking:  \n   $$\n   L_{\\text{total}}(P) = \\sum_{(p,q) \\in L} \\sum_{i=1}^3 \\mathbf{1}_{\\{p, q \\in T_i\\}}\n   $$\n   (i.e., count every directed pair $ (p,q) \\in L $ where $ p $ and $ q $ are in the same team; if both $ (p,q) $ and $ (q,p) \\in L $, count both)\n\n**Output**  \nTwo integers:  \n- Minimal possible $ \\Delta(P, \\sigma) $  \n- Maximal $ L_{\\text{total}}(P) $ over all $ (P, \\sigma) $ achieving the minimal $ \\Delta(P, \\sigma) $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF77A","tags":["brute force","implementation"],"sample_group":[["3\nTroll likes Dracul\nDracul likes Anka\nSnowy likes Hexadecimal\n210 200 180","30 3"],["2\nAnka likes Chapay\nChapay likes Anka\n10000 50 50","1950 2"]],"created_at":"2026-03-03 11:00:39"}}