{"raw_statement":[{"iden":"statement","content":"You live in a graph G, with N vertices and M edges. P of these vertices have gangsters living on them. You owe each gangster some money, given by the array C (of size P). You wish to travel from s to t. If you step within distance k of any gangster who you haven't paid, you die. We define the length of a path as then number of edges it comprises. We define the distance of two nodes as the length of the shortest path connecting them. Further, we define the cost of travelling as the sum of gangster debts you pay off. Of course, you wish to minimise the cost of travelling from s to t without dying. Note that you may not die at s or t either.\n\nFirst line contains four integers, N, M, P, and K. (1 ≤ N, M, K ≤ 105, 1 ≤ P ≤ 10)  Second line contains P integers, the locations of the gangsters.  Third line contains P integers, the array C (1 ≤ Ci ≤ 109)  Each of the next M line contains two integers, xi and yi, which mean that there exists an edge between the nodes xi and yi.  The last line contains two integers, s and t, the source and the target.  It is guaranteed that a solution always exists.\n\nA single integer, the minimum cost of travelling from s to t.\n\nFor the given example, the graph looks like    Note that the gangster is at distance 1 from the nodes 5 and 3, both of which must be visited.\n\n"},{"iden":"input","content":"First line contains four integers, N, M, P, and K. (1 ≤ N, M, K ≤ 105, 1 ≤ P ≤ 10)  Second line contains P integers, the locations of the gangsters.  Third line contains P integers, the array C (1 ≤ Ci ≤ 109)  Each of the next M line contains two integers, xi and yi, which mean that there exists an edge between the nodes xi and yi.  The last line contains two integers, s and t, the source and the target.  It is guaranteed that a solution always exists."},{"iden":"output","content":"A single integer, the minimum cost of travelling from s to t."},{"iden":"note","content":"For the given example, the graph looks like    Note that the gangster is at distance 1 from the nodes 5 and 3, both of which must be visited."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ |V| = N $, $ |E| = M $.  \nLet $ \\mathcal{G} = \\{g_1, g_2, \\dots, g_P\\} \\subseteq V $ be the set of gangster locations.  \nLet $ C = (c_1, c_2, \\dots, c_P) \\in \\mathbb{Z}_{>0}^P $ be the cost array, where $ c_i $ is the debt to gangster at $ g_i $.  \nLet $ k \\in \\mathbb{Z}_{>0} $ be the safe distance threshold.  \nLet $ s, t \\in V $ be the source and target vertices.\n\n**Constraints**  \n1. $ 1 \\leq N, M, K \\leq 10^5 $, $ 1 \\leq P \\leq 10 $  \n2. For all $ i \\in \\{1, \\dots, P\\} $, $ 1 \\leq c_i \\leq 10^9 $  \n3. The graph is connected and a valid path from $ s $ to $ t $ exists.  \n4. You may not die at $ s $ or $ t $: $ \\text{dist}(s, g_i) > k $ and $ \\text{dist}(t, g_i) > k $ for all $ i $.  \n\n**Objective**  \nMinimize the total cost $ \\sum_{i \\in I} c_i $, where $ I \\subseteq \\{1, \\dots, P\\} $ is the set of gangsters paid, such that there exists a path $ \\pi $ from $ s $ to $ t $ where for every vertex $ v \\in \\pi $,  \n$$\n\\min_{i \\notin I} \\text{dist}(v, g_i) > k\n$$  \n(i.e., all gangsters not paid are at distance > $ k $ from every vertex on the path).","simple_statement":"You are in a graph with N nodes and M edges. P gangsters live on P nodes, each demanding a payment C[i]. You must go from node s to node t. If you come within K distance of any unpaid gangster, you die. You can pay any subset of gangsters to avoid danger. Find the minimum total payment to safely reach t from s.","has_page_source":false}