{"trustable":true,"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":"\u003cp\u003e物流公司与某公司达成协议,要把一大批货物分$$$n$$$天从A地(编号1)运输向B工厂(编号$$$m$$$),由于物流公司的信誉不太好,甲方公司要求沿路需要设置人员监管,每条道路由相应的监管成本。\u003c/p\u003e\u003cp\u003e为了监管的方便,一般固定一条路线运输,但是有些时候由于地方施工,某些城市无法通行。\u003c/p\u003e\u003cp\u003e修改路线是一件十分麻烦的事情,需要重新安排沿路的监管工作,所以会消耗$$$k$$$的成本更换监管方案。\u003c/p\u003e\u003cp\u003e政府会发布公告,告知这些天的地方施工情况,方便进行运输道路规划。\u003c/p\u003e\u003cp\u003e希望你能够帮忙订一个$$$n$$$天的运输计划,使得总监管成本尽可能地小。\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e第一行输入$$$n,m,k,e(n \\leq 100, m \\leq 20, e \\leq 190)$$$分别代表运输计划$$$n$$$天,一共$$$m$$$个城市,更换监管安排的成本$$$k$$$,以及$$$e$$$条道路连接各城市。\u003c/p\u003e\u003cp\u003e接下来$$$e$$$行,每行输入$$$u,v,w$$$,表示一条连接$$$u,v$$$两城市的道路,该道路监管成本$$$w$$$。\u003c/p\u003e\u003cp\u003e接下来一行输入一个数$$$p(p \\leq 1000)$$$,表示政府公告数量。\u003c/p\u003e\u003cp\u003e接下来的$$$p$$$行,每行输入$$$x,a,b$$$,表示城市$$$x$$$在$$$a$$$到$$$b$$$天会施工无法通行。(包括$$$a,b$$$)\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e一个整数,表示总的运输计划所需的最小监管成本。\u003c/p\u003e\u003cp\u003e若由于施工原因无法完成运输输出\"-1\"(不含引号)。\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 5 10 8\n1 2 1\n1 3 3\n1 4 2\n2 3 2\n2 4 4\n3 4 1\n3 5 2\n4 5 2\n4\n2 2 3\n3 1 1\n3 3 3\n4 4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e32\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003e样例解释:\u003c/p\u003e\u003cp\u003e前三天走1-4-5\u003c/p\u003e\u003cp\u003e后两天走1-3-5\u003c/p\u003e\u003cp\u003e总成本为(2+2)*3+(3+2)*2+10\u003d32\u003c/p\u003e"}}]}