{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"В день детей ребенок получил в подарок от Delayyy игрушку. Но ребенок такой вредный, что он ждет — не дождется шанса сломать ее.\u003cbr\u003e\n\u003cbr\u003e\nИгрушка состоит из n деталей, соединенных m веревочками. Каждая веревочка соединяет две детали, при этом каждая пара деталей соединена не более чем одной веревочкой. Чтобы разломать игрушку, ребенок должен оторвать все ее детали. Ребенок может отрывать по одной детали за раз, на каждое отрывание он тратит энергию. Обозначим значение энергии детали i как v i. Ребенок тратит v f 1 + v f 2 + ... + v f k энергии на отрывание детали i, где f 1, f 2, ..., f k — еще не оторванные детали, напрямую соединенные веревочками с i-й.\n\u003cbr\u003e\u003cbr\u003e\nПомогите ребенку посчитать минимальную суммарную энергию, которую он должен потратить на отрывание всех n деталей."}},{"title":"Input","value":{"format":"HTML","content":"В первой строке записано два целых числа, n и m (1 ≤ n ≤ 1000; 0 ≤ m ≤ 2000). Во второй строке записано n целых чисел: v 1, v 2, ..., v n (0 ≤ v i ≤ 10^5). Затем следует m строк, в каждой записано по два целых числа, x i и y i, обозначающих веревочку, соединяющую детали x i и y i (1 ≤ x i, y i ≤ n; x i ≠ y i).\n\u003cbr\u003e\u003cbr\u003e\nСчитайте, что все детали пронумерованы от 1 до n."}},{"title":"Output","value":{"format":"HTML","content":"Выведите минимальную суммарную энергию, необходимую для отрывания всех n деталей игрушки."}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e4 3\u003cbr\u003e10 20 30 40\u003cbr\u003e1 4\u003cbr\u003e1 2\u003cbr\u003e2 3\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e40\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e4 4\u003cbr\u003e100 100 100 100\u003cbr\u003e1 2\u003cbr\u003e2 3\u003cbr\u003e2 4\u003cbr\u003e3 4\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e400\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e7 10\u003cbr\u003e40 10 20 10 20 80 40\u003cbr\u003e1 5\u003cbr\u003e4 7\u003cbr\u003e4 5\u003cbr\u003e5 2\u003cbr\u003e5 7\u003cbr\u003e6 4\u003cbr\u003e1 6\u003cbr\u003e1 3\u003cbr\u003e4 3\u003cbr\u003e1 4\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e160\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"Одна из оптимальных последовательностей действий в первом примере такова:\n\u003cbr\u003e\u003cbr\u003e\nСначала оторвите деталь 3, затрата энергии равна 20.\u003cbr\u003e\nЗатем оторвите деталь 2, затрата энергии равна 10.\u003cbr\u003e\nПотом оторвите деталь 4, затрата энергии равна 10.\u003cbr\u003e\nНаконец, оторвите деталь 1, затрата энергии равна 0.\u003cbr\u003e\nТаким образом, всего ребенок затрачивает 20 + 10 + 10 + 0 \u003d 40 единиц энергии, это минимально возможный ответ.\n\u003cbr\u003e\u003cbr\u003e\nВо втором примере ребенок потратит 400 единиц энергии вне зависимости от порядка отрывания деталей."}}]}