{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e Timon is the leader of a small group of meerkats living in southern Namibia. The meerkats are using an intricate system \nof underground, multi-level tunnels to hide from predators and the scorching heat of the day. Their most feared predators are the bat-eared foxes, which can dig out ground, but only up to a certain depth.\n\u003c/p\u003e\n\n\u003cp\u003e\n The meerkats have dug \u003cspan class\u003d\"tex2jax_process\"\u003e$N$ \u003c/span\u003e pits in the ground, connected by \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e bidirectional tunnels. For each pit \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e we know the number of meerkats \u003cspan class\u003d\"tex2jax_process\"\u003e$P_i$\u003c/span\u003e currently residing inside.\n\u003c/p\u003e\n\n\u003cp\u003e\n Most pits are close to the surface, and thus vulnerable to inquisitive foxes. However, there are \u003cspan class\u003d\"tex2jax_process\"\u003e$S$\u003c/span\u003e special pits which are so deep that no fox can reach them. Nevertheless, each of these special pits has a limit on the number of meerkats that can safely hide inside.\n\u003c/p\u003e\n\n\u003cp\u003e\nWhen Timon rings the alarm, all meerkats will run to one of the special pits. He knows that there is always going to be \nenough room for each meerkat to hide and that all the special pits are accessible from any other pit. However, he wants\nto know what is the minimum amount of time required until all meerkats are safe. \n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e \n\u003cul class\u003d\"itemize\"\u003e \n \u003cli\u003e \u003cp\u003e\n The first line contains three integers: the number of pits \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq N \\leq 10^5$\u003c/span\u003e), the number of tunnels \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq M \\leq 2 * 10^5$\u003c/span\u003e) and the number of special pits \u003cspan class\u003d\"tex2jax_process\"\u003e$S$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq S \\leq 10$\u003c/span\u003e).\n \u003c/p\u003e \u003c/li\u003e \n\n \u003cli\u003e\u003cp\u003e\n The second line has \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e integers, indicating the number \u003cspan class\u003d\"tex2jax_process\"\u003e$P_i$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq P_i \\leq 10^9$\u003c/span\u003e) of meerkats currently living in pit \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e. \n \u003c/p\u003e\u003c/li\u003e\n \n \u003cli\u003e\u003cp\u003e\n Each of the next \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e lines contains three integers: \u003cspan class\u003d\"tex2jax_process\"\u003e$u, v$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq u, v \\leq N$\u003c/span\u003e) and \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq w \\leq 10^9$\u003c/span\u003e). This indicates that there is a bidirectional tunnel connecting pit \u003cspan class\u003d\"tex2jax_process\"\u003e$u$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$v$\u003c/span\u003e that requires \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e time units to traverse. For any two pits there is at most one tunnel connecting them directly and no tunnel connects a pit to itself. \n \u003c/p\u003e\u003c/li\u003e\n\n \u003cli\u003e\u003cp\u003e\n The following \u003cspan class\u003d\"tex2jax_process\"\u003e$S$\u003c/span\u003e lines contains two integers, \u003cspan class\u003d\"tex2jax_process\"\u003e$s_j$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$c_j$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq s_j \\leq N$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq c_j \\leq 10^9$\u003c/span\u003e), indicating that pit \u003cspan class\u003d\"tex2jax_process\"\u003e$s_j$\u003c/span\u003e is a special pit, with a maximum capacity of \u003cspan class\u003d\"tex2jax_process\"\u003e$c_j$\u003c/span\u003e meerkats. \n \u003c/p\u003e\u003c/li\u003e \n\u003c/ul\u003e \n\n\u003ch2\u003eOutput\u003c/h2\u003e \n\u003cp\u003eDisplay the minimum amount of time required until all meerkats are safe.\u003c/p\u003e \n\n\u003ctable class\u003d\"sample\" summary\u003d\"sample data\"\u003e \n \u003ctbody\u003e\n \u003ctr\u003e \n \u003cth\u003eSample Input 1\u003c/th\u003e \n \u003cth\u003eSample Output 1\u003c/th\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003e \u003cpre\u003e2 1 1\n3 2\n2 1 5\n1 7\n\u003c/pre\u003e \u003c/td\u003e \n \u003ctd\u003e \u003cpre\u003e5\n\u003c/pre\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e\n\u003c/table\u003e \n\u003ctable class\u003d\"sample\" summary\u003d\"sample data\"\u003e \n \u003ctbody\u003e\n \u003ctr\u003e \n \u003cth\u003eSample Input 2\u003c/th\u003e \n \u003cth\u003eSample Output 2\u003c/th\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003e \u003cpre\u003e4 5 2\n2 0 0 2\n2 1 6\n3 2 3\n4 3 4\n3 1 2\n2 4 6\n2 2\n3 2\n\u003c/pre\u003e \u003c/td\u003e \n \u003ctd\u003e \u003cpre\u003e5\n\u003c/pre\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e\n\u003c/table\u003e \n\u003ctable class\u003d\"sample\" summary\u003d\"sample data\"\u003e \n \u003ctbody\u003e\n \u003ctr\u003e \n \u003cth\u003eSample Input 3\u003c/th\u003e \n \u003cth\u003eSample Output 3\u003c/th\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003e \u003cpre\u003e7 8 3\n0 1 1 1 1 0 2\n2 1 1\n6 7 10\n7 5 3\n3 2 1\n1 3 1\n4 6 5\n3 4 1\n6 5 3\n1 1\n2 1\n6 5\n\u003c/pre\u003e \u003c/td\u003e \n \u003ctd\u003e \u003cpre\u003e6\n\u003c/pre\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e\n\u003c/table\u003e \n\u003ctable class\u003d\"sample\" summary\u003d\"sample data\"\u003e \n \u003ctbody\u003e\n \u003ctr\u003e \n \u003cth\u003eSample Input 4\u003c/th\u003e \n \u003cth\u003eSample Output 4\u003c/th\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003e \u003cpre\u003e2 1 1\n0 10\n2 1 1000000000\n2 10\n\u003c/pre\u003e \u003c/td\u003e \n \u003ctd\u003e \u003cpre\u003e0\n\u003c/pre\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e\n\u003c/table\u003e"}}]}