{"raw_statement":[{"iden":"statement","content":"小白非常喜欢玩 \"县际争霸\" 这款游戏，虽然他的技术并不容乐观。\"县际争霸\" 的地图共有两个县，每个县里各有 $n$ 个据点。同一个县之间的据点是互不连通的，两个县之间的据点也是互不连通的。小白的 $p$ 个战斗单位在第一个县的第 $x_1, x_2, \\\\\\\\cdots, x_p$ 个据点中，而对手的 $q$ 个建筑单位在第二个县第 $y_1, y_2, \\\\\\\\cdots, y_q$ 个据点中。\n\n为了发起进攻，小白建造了很多的 \"折跃棱镜\"。折跃棱镜可以帮助小白的单位在两个县之间移动，而且可以有多个单位同时通过折跃棱镜。具体地说，一个折跃棱镜包含有 $5$ 个参数信息 $a, b, c, d, w$，代表位于第一个县任意第 $x \" \"(a <= x <= b)$ 个据点的战斗单位可以花费 $w$ 单位时间到达第二个县的任意第 $y \" \"(c <= y <= d)$ 个据点。折跃棱镜的通道是双向的，所以位于第二个县任意第 $y \" \"(c <= y <= d)$ 个据点的战斗单位也可以花费 $w$ 单位时间到达第一个县的任意第 $x \" \"(a <= x <= b)$ 个据点。\n\n如果一个小白的战斗单位到达了一个有敌方建筑单位的据点，那么这个战斗单位就会即刻投入战斗。当小白所有的战斗单位都投入了战斗之后，对手会感觉到压力太大而主动投降。小白想尽快结束这场战斗，请聪明的你帮他算一算，如果采用最优的调度策略，对手最早将在什么时刻投降（假设当前局面是零时刻）。如果存在战斗单位始终无法投入战斗，则请输出_boring game_。\n\n输入共 $m + 3$ 行，第一行输入四个正整数 $n, m, p, q \" \"(1 <= n, m, p, q <= 10^5)$ 由空格间隔开，分别表示每个县的据点数量、折跃棱镜数量、小白的战斗单位数量和对手的建筑单位数量。\n\n接下来的 $m$ 行中，第 $i$ 行输入五个正整数 $a_i, b_i, c_i, d_i, w_i \" \"(1 <= a_i <= b_i <= n, 1 <= c_i <= d_i <= n, 1 <= w_i <= 10^9)$ 由空格间隔开，表示第 $i$ 个折跃棱镜的参数，具体含义见题目描述。\n\n接下来一行输入 $p$ 个正整数 $x_1, x_2, \\\\\\\\cdots, x_p \" \"(1 <= x_i <= n)$ 由空格间隔开，分别表示小白的战斗单位所在的据点位置。\n\n最后一行输入 $q$ 个正整数 $y_1, y_2, \\\\\\\\cdots, y_q \" \"(1 <= y_i <= n)$ 由空格间隔开，分别表示对手的建筑单位所在的据点。\n\n如果对手最终会主动投降，则请输出一个非负整数，表示在小白的最优调度策略下对手最早的投降时间；如果存在战斗单位始终无法投入战斗，则请输出_boring game_。\n\n样例中，一种最优调度策略是：第一个战斗单位从第一县的 $2$ 号据点折跃到第二县的 $4$ 号据点即可投入战斗，这将花费 $2$ 单位时间，同时第二个战斗单位从第一县的 $3$ 号据点折跃到第二县的 $3$ 号据点再折跃到第一县的 $2$ 号据点最后折跃到第二县的 $4$ 号据点也可投入战斗，这将花费 $4$ 单位时间。\n\n"},{"iden":"input","content":"输入共 $m + 3$ 行，第一行输入四个正整数 $n, m, p, q \" \"(1 <= n, m, p, q <= 10^5)$ 由空格间隔开，分别表示每个县的据点数量、折跃棱镜数量、小白的战斗单位数量和对手的建筑单位数量。接下来的 $m$ 行中，第 $i$ 行输入五个正整数 $a_i, b_i, c_i, d_i, w_i \" \"(1 <= a_i <= b_i <= n, 1 <= c_i <= d_i <= n, 1 <= w_i <= 10^9)$ 由空格间隔开，表示第 $i$ 个折跃棱镜的参数，具体含义见题目描述。接下来一行输入 $p$ 个正整数 $x_1, x_2, \\\\\\\\cdots, x_p \" \"(1 <= x_i <= n)$ 由空格间隔开，分别表示小白的战斗单位所在的据点位置。最后一行输入 $q$ 个正整数 $y_1, y_2, \\\\\\\\cdots, y_q \" \"(1 <= y_i <= n)$ 由空格间隔开，分别表示对手的建筑单位所在的据点。"},{"iden":"output","content":"如果对手最终会主动投降，则请输出一个非负整数，表示在小白的最优调度策略下对手最早的投降时间；如果存在战斗单位始终无法投入战斗，则请输出_boring game_。"},{"iden":"note","content":"样例中，一种最优调度策略是：第一个战斗单位从第一县的 $2$ 号据点折跃到第二县的 $4$ 号据点即可投入战斗，这将花费 $2$ 单位时间，同时第二个战斗单位从第一县的 $3$ 号据点折跃到第二县的 $3$ 号据点再折跃到第一县的 $2$ 号据点最后折跃到第二县的 $4$ 号据点也可投入战斗，这将花费 $4$ 单位时间。"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, p, q \\in \\mathbb{Z}^+ $ denote:  \n- number of outposts per county,  \n- number of warp prisms,  \n- number of White's combat units,  \n- number of opponent's buildings.  \n\nLet $ \\mathcal{W} = \\{ (a_i, b_i, c_i, d_i, w_i) \\}_{i=1}^m $ be the set of warp prisms, where each prism enables bidirectional travel:  \n- from any outpost $ x \\in [a_i, b_i] $ in County 1 to any outpost $ y \\in [c_i, d_i] $ in County 2,  \n- in time $ w_i $.  \n\nLet $ X = \\{ x_1, \\dots, x_p \\} \\subseteq [1, n] $ be the set of initial outpost positions of White’s combat units.  \nLet $ Y = \\{ y_1, \\dots, y_q \\} \\subseteq [1, n] $ be the set of outpost positions containing opponent’s buildings.  \n\nDefine a bipartite graph $ G = (U \\cup V, E) $:  \n- $ U = [1, n] $: outposts in County 1,  \n- $ V = [1, n] $: outposts in County 2,  \n- For each prism $ (a, b, c, d, w) \\in \\mathcal{W} $, add edges:  \n  - $ \\forall u \\in [a, b], \\forall v \\in [c, d] $: edge $ (u, v) $ with weight $ w $,  \n  - $ \\forall v \\in [c, d], \\forall u \\in [a, b] $: edge $ (v, u) $ with weight $ w $.  \n\n**Constraints**  \n1. $ 1 \\le n, m, p, q \\le 10^5 $  \n2. $ 1 \\le a_i \\le b_i \\le n $, $ 1 \\le c_i \\le d_i \\le n $, $ 1 \\le w_i \\le 10^9 $  \n3. $ x_i, y_j \\in [1, n] $ for all $ i, j $  \n\n**Objective**  \nCompute the minimal time $ T $ such that **every** combat unit in $ X $ can reach **at least one** outpost in $ Y $ via a path in $ G $, and $ T $ is the **minimum possible maximum travel time** over all units (i.e., minimize the makespan).  \n\nIf any unit in $ X $ cannot reach any outpost in $ Y $, output `boring game`.  \nOtherwise, output $ T = \\min_{\\text{assignments}} \\max_{i \\in [1,p]} \\text{dist}(x_i, Y) $,  \nwhere $ \\text{dist}(x_i, Y) = \\min_{y \\in Y} \\text{shortest-path}(x_i, y) $.","simple_statement":"小白有 p 个单位在第一个县的某些据点，对手有 q 个建筑在第二个县的某些据点。  \n有 m 个“折跃棱镜”，每个棱镜连接第一个县的 [a,b] 所有据点 和 第二个县的 [c,d] 所有据点，花费 w 时间双向通行。  \n\n单位可以通过多个棱镜多次折跃。  \n当一个单位到达任意一个有敌方建筑的据点，就立刻战斗。  \n\n问：所有单位都能战斗的最短时间是多少？  \n如果有人永远到不了敌方据点，输出 \"boring game\"。","has_page_source":false}