{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e对于一些实验,小Petya需要一个同步加速器。他已经有了这个设备,现在剩下的就是设置燃料供应。燃料通过从节点\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e到\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e编号的节点系统,并通过管道连接。管道从每个较小编号的节点到每个较大编号的节点。燃料只能沿着管道从较小编号的节点流向较大编号的节点。任意数量的燃料可以从第一个节点进入,最后一个节点直接连接到同步加速器。已知每根管道有三个属性:应通过管道的最小燃料量、可能通过管道的最大燃料量和管道激活的成本。如果从节点\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e到节点\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e流动\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eij\u003c/i\u003e\u003c/sub\u003e \u0026gt; 0\u003c/span\u003e单位的燃料,将花费\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eij\u003c/i\u003e\u003c/sub\u003e + \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eij\u003c/i\u003e\u003c/sub\u003e\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e\u003c/span\u003e图格里克(\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eij\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e是管道激活的成本),如果燃料不通过管道流动,则不会产生任何费用。每根管道只能通过整数单位的燃料。\u003c/p\u003e\u003cp\u003e对管道的最小和最大燃料容量的约束总是存在的,不仅仅在管道激活时。可以假设只有当通过管道的流量严格大于零时,管道才处于激活状态。\u003c/p\u003e\u003cp\u003ePetya不希望管道系统过载,因此他希望找到进入第一个节点后能到达同步加速器的最小燃料量。此外,他希望给赞助商留下深刻印象,因此必须尽可能多地支付通过每根管道的燃料费用总和。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含整数\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 6\u003c/span\u003e),表示节点的数量。接下来的\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e(\u003ci\u003en\u003c/i\u003e - 1) / 2\u003c/span\u003e行中,每行包含五个整数\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e, \u003ci\u003ef\u003c/i\u003e, \u003ci\u003el\u003c/i\u003e, \u003ci\u003eh\u003c/i\u003e, \u003ci\u003ea\u003c/i\u003e\u003c/span\u003e,描述管道:管道的第一个节点、管道的第二个节点、可以通过管道流动的最小和最大燃料量以及激活成本,分别为\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003es\u003c/i\u003e \u0026lt; \u003ci\u003ef\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e, 0 ≤ \u003ci\u003el\u003c/i\u003e ≤ \u003ci\u003eh\u003c/i\u003e ≤ 5, 0 ≤ \u003ci\u003ea\u003c/i\u003e ≤ 6\u003c/span\u003e。保证对于每对不同编号的节点,输入中描述的它们之间将恰好有一根管道。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e在第一行输出两个用空格分隔的数字:可以流入同步加速器的最小可能燃料量,以及为了使该燃料量到达同步加速器而需要支付的最大可能总和。如果没有燃料可以到达同步加速器,则输出“\u003cspan class\u003d\"tex-font-style-tt\"\u003e-1 -1\u003c/span\u003e”。\u003c/p\u003e\u003cp\u003e流入同步加速器的燃料量不一定是正数。如果每根管道的最小约束都等于零,则可以等于零。\u003c/p\u003e"}},{"title":"示例","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\u003e2\n1 2 1 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","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\u003e3\n1 2 1 2 3\n1 3 0 0 0\n2 3 3 4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1 -1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","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\u003e4\n1 2 0 2 1\n2 3 0 2 1\n1 3 0 2 6\n1 4 0 0 1\n2 4 0 0 0\n3 4 2 3 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 15\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","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\u003e3\n1 2 0 2 1\n1 3 1 2 1\n2 3 1 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个测试中,我们可以从节点1传输1或2单位的燃料到节点2。最小可能量为1,成本为\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e12\u003c/sub\u003e + 1\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e \u003d 4\u003c/span\u003e。\u003c/p\u003e\u003cp\u003e在第二个测试中,你最多可以从节点1传输2单位到节点2,并且你必须至少从节点2传输3单位到节点3。这是不可能的。\u003c/p\u003e\u003cp\u003e在第三个测试中,最小可能量为2。你可以通过两条不同路径传输每单位燃料:1-\u003e2-\u003e3-\u003e4或1-\u003e3-\u003e4。如果你使用第一条路径两次,成本为\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e12\u003c/sub\u003e + 2\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e + \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e23\u003c/sub\u003e + 2\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e + \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e34\u003c/sub\u003e + 2\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e\u003c/span\u003e\u003d14。如果你使用第二条路径两次,成本为\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e13\u003c/sub\u003e + 2\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e + \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e34\u003c/sub\u003e + 2\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e\u003c/span\u003e\u003d14。然而,如果你使用每条路径(允许一单位燃料通过管道1-\u003e2、2-\u003e3、1-\u003e3,两单位燃料通过3-\u003e4),成本为\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e12\u003c/sub\u003e + 1\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e + \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e23\u003c/sub\u003e + 1\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e + \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e13\u003c/sub\u003e + 1\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e + \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e34\u003c/sub\u003e + 2\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e\u003c/span\u003e\u003d15,这是最大可能成本。\u003c/p\u003e\u003cp\u003e还要注意,由于没有燃料从节点1流向节点4,因此不会将该管道的激活成本添加到答案中。\u003c/p\u003e"}}]}