{"problem":{"name":"Skiing","description":{"content":"AtCoder Ski Area has $N$ open spaces called Space $1$, Space $2$, $\\ldots$, Space $N$. The altitude of Space $i$ is $H_i$. There are $M$ slopes that connect two spaces bidirectionally. The $i$\\-th slo","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc237_e"},"statements":[{"statement_type":"Markdown","content":"AtCoder Ski Area has $N$ open spaces called Space $1$, Space $2$, $\\ldots$, Space $N$. The altitude of Space $i$ is $H_i$. There are $M$ slopes that connect two spaces bidirectionally. The $i$\\-th slope $(1 \\leq i \\leq M)$ connects Space $U_i$ and Space $V_i$. It is possible to travel between any two spaces using some slopes.\nTakahashi can only travel between spaces by using slopes. Each time he goes through a slope, his **happiness** changes. Specifically, when he goes from Space $X$ to Space $Y$ by using the slope that directly connects them, his happiness changes as follows.\n\n*   If the altitude of Space $X$ is strictly higher than that of Space $Y$, the happiness **increases** by their difference: $H_X-H_Y$.\n*   If the altitude of Space $X$ is strictly lower than that of Space $Y$, the happiness **decreases** by their difference multiplied by $2$: $2(H_Y-H_X)$.\n*   If the altitude of Space $X$ is equal to that of Space $Y$, the happiness does not change.\n\nThe happiness may be a negative value.\nInitially, Takahashi is in Space $1$, and his happiness is $0$. Find his maximum possible happiness after going through any number of slopes (possibly zero), ending in any space.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2\\times 10^5$\n*   $N-1 \\leq M \\leq \\min( 2\\times 10^5,\\frac{N(N-1)}{2})$\n*   $0 \\leq H_i\\leq 10^8$ $(1 \\leq i \\leq N)$\n*   $1 \\leq U_i < V_i \\leq N$ $(1 \\leq i \\leq M)$\n*   $(U_i,V_i) \\neq (U_j, V_j)$ if $i \\neq j$.\n*   All values in input are integers.\n*   It is possible to travel between any two spaces using some slopes.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$H_1$ $H_2$ $\\ldots$ $H_N$\n$U_1$ $V_1$\n$U_2$ $V_2$\n$\\vdots$\n$U_M$ $V_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc237_e","tags":[],"sample_group":[["4 4\n10 8 12 5\n1 2\n1 3\n2 3\n3 4","3\n\nIf Takahashi takes the route Space $1$ $\\to$ Space $3$ $\\to$ Space $4$, his happiness changes as follows.\n\n*   When going from Space $1$ (altitude $10$) to Space $3$ (altitude $12$), it decreases by $2\\times (12-10)=4$ and becomes $0-4=-4$.\n*   When going from Space $3$ (altitude $12$) to Space $4$ (altitude $5$), it increases by $12-5=7$ and becomes $-4+7=3$.\n\nIf he ends the travel here, the final happiness will be $3$, which is the maximum possible value."],["2 1\n0 10\n1 2","0\n\nHis happiness is maximized by not moving at all."]],"created_at":"2026-03-03 11:01:13"}}