{"problem":{"name":"C. Ramzi","description":{"content":"Ramzi -Aufa's best friend- lives in the city of Rainland, Rainland is a very ordinary city except for one thing. It has a very Bad Weather! The city is described as a set of intersections and a set o","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10106C"},"statements":[{"statement_type":"Markdown","content":"Ramzi -Aufa's best friend- lives in the city of Rainland, Rainland is a very ordinary city except for one thing. It has a very Bad Weather!\n\nThe city is described as a set of intersections and a set of connections. Each pair of intersections is either connected with a cars-road, or with a pedestrian-road. Some pairs has a cars-road and a pedestrian-road connecting them and some pairs doesn't has any roads between them at all. You can assume that no pair has more than one pedestrian-road or more than one cars-road.\n\nRamzi can get a taxi to go from intersection A to intersection B if A and B has a cars-road connecting them, but he has to walk if it's a pedestrian road. Mostly he will be walking in the rain!\n\nRamzi is in intersection x and he want to meet Aufa in intersection y. Your job is to help him find the _Optimal path_ form x to y.\n\nThe _Optimal path_ is described as the path with the minimum walking time. If there is more than one path with the same minimum walking time, the _Optimal path_ is the one with the minimum total time. The walking time for any path is the sum of the pedestrian-roads' time that occur in the path.\n\nThe total time for any path is the sum of its roads's time \"pedestrian-roads and cars-roads\" .\n\nYou can assume that Ramzi doesn't get wet when he is waiting for the taxi in some intersection, so we aren't interested in the waiting time for the taxi. Also he cant't walk throw any cars-road. So if he want to use a cars-road, he must take a taxi.\n\nThe first line of the input will contain T the number of test cases.\n\nEach test case starts with two integers on a single line (0 < N ≤ 100), the number of the intersections, (0 < M ≤ N * (N - 1)), the number of the connections.\n\nThen M lines follow, each describes a connection and contains four integers (0 < a ≤ N) , (0 < b ≤ N) , (0 ≤ c ≤ 10000) , (). Which means that there is a connection between intersection a and intersection b that takes c minute of time. However if k is equal to 1 then it's a pedestrian-road, otherwise it's a cars-road. All connections are bidirectional. Meaning that you can use it to go both from a to b and from b to a. It's guaranteed that (a ≠ b).\n\nFollows a line containing two integers (0 < x ≤ N), (0 < y ≤ N). which means that we are interested in the optimal path between intersection x and intersection y. It's guaranteed that (x ≠ y).\n\nFor each test case, if there is a path between x and y, you should print two integers on a separated line. \n\nThe first one should be the walking time in the optimal path. The second one should be the total time of the optimal path. If there isn't any path between x and y then you should print -1 on a separated line. See the sample output for more details.\n\nLarge I/O files. Please consider using fast input/output methods.\n\n## Input\n\nThe first line of the input will contain T the number of test cases.Each test case starts with two integers on a single line (0 < N ≤ 100), the number of the intersections, (0 < M ≤ N * (N - 1)), the number of the connections.Then M lines follow, each describes a connection and contains four integers (0 < a ≤ N) , (0 < b ≤ N) , (0 ≤ c ≤ 10000) , (). Which means that there is a connection between intersection a and intersection b that takes c minute of time. However if k is equal to 1 then it's a pedestrian-road, otherwise it's a cars-road. All connections are bidirectional. Meaning that you can use it to go both from a to b and from b to a. It's guaranteed that (a ≠ b).Follows a line containing two integers (0 < x ≤ N), (0 < y ≤ N). which means that we are interested in the optimal path between intersection x and intersection y. It's guaranteed that (x ≠ y).\n\n## Output\n\nFor each test case, if there is a path between x and y, you should print two integers on a separated line. The first one should be the walking time in the optimal path. The second one should be the total time of the optimal path. If there isn't any path between x and y then you should print -1 on a separated line. See the sample output for more details.\n\n[samples]\n\n## Note\n\nLarge I/O files. Please consider using fast input/output methods.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ H, W \\in \\mathbb{Z} $ denote the height and width of the grid.  \nLet $ E = (e_1, e_2, \\dots, e_H) $ and $ W = (w_1, w_2, \\dots, w_H) $ be sequences of positive integers representing the widths of the east and west walls at each row $ i \\in \\{1, \\dots, H\\} $, respectively.  \n\n**Constraints**  \n1. $ 2 \\leq H \\leq 10^5 $  \n2. $ 4 \\leq W \\leq 10^5 $  \n3. For all $ i \\in \\{1, \\dots, H\\} $, $ e_i \\geq 1 $, $ w_i \\geq 1 $, and $ e_i + w_i \\leq W $ (walls do not overlap initially).  \n4. Both walls move toward each other at speed $ 1 \\, \\text{m/s} $.  \n\n**Objective**  \nCompute the time $ t \\in \\mathbb{R}^+ $ at which the east and west walls first collide, i.e., the minimum time such that for some row $ i $, the sum of the remaining widths of the two walls becomes zero:  \n$$\nt = \\min_{i \\in \\{1, \\dots, H\\}} \\left( \\frac{W - e_i - w_i}{2} \\right)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10106C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}