{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\u0026nbsp;\u0026nbsp;A new candy factory opens in pku-town. The factory import M machines to produce high quality candies. These machines are numbered from 1 to M.\u003cbr\u003e\u0026nbsp;\u0026nbsp;There are N candies need to be produced. These candies are also numbered from 1 to N. For each candy i , it can be produced in any machine j. It also has a producing time(s\u003csub\u003ei\u003c/sub\u003e,t\u003csub\u003ei\u003c/sub\u003e) , meaning that candy i must start producing at time s\u003csub\u003ei\u003c/sub\u003e and will finish at t\u003csub\u003ei\u003c/sub\u003e. Otherwise if the start time is p\u003csub\u003ei\u003c/sub\u003e(s\u003csub\u003ei\u003c/sub\u003e \u0026lt; p\u003csub\u003ei\u003c/sub\u003e \u0026lt; t\u003csub\u003ei\u003c/sub\u003e) then candy will still finish at t\u003csub\u003ei\u003c/sub\u003e but need additional K*(p\u003csub\u003ei\u003c/sub\u003e - s\u003csub\u003ei\u003c/sub\u003e) cost. The candy can’t be produced if p\u003csub\u003ei\u003c/sub\u003e is greater than or equal to t\u003csub\u003ei\u003c/sub\u003e. Of course one machine can only produce at most one candy at a time and can’t stop once start producing.\u003cbr\u003e\u0026nbsp;\u0026nbsp;On the other hand, at time 0 all the machines are in their initial state and need to be “set up” or changed before starting producing. To set up Machine j from its initial state to the state which is suitable for producing candiy i, the time required is C\u003csub\u003eij\u003c/sub\u003e and cost is D\u003csub\u003eij\u003c/sub\u003e. To change a machine from the state suitable for candy i\u003csub\u003e1\u003c/sub\u003e into the state suitable for candy i\u003csub\u003e2\u003c/sub\u003e, time required is E\u003csub\u003ei1i2\u003c/sub\u003e and cost is F\u003csub\u003ei1i2\u003c/sub\u003e.\u003cbr\u003e\u0026nbsp;\u0026nbsp;As the manager of the factory you have to make a plan to produce all the N candies. While the sum of producing cost should be minimized.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" There are multiple test cases.\u003cbr\u003e For each case, the first line contains three integers N(1\u0026lt;\u003dN\u0026lt;\u003d100), M(1\u0026lt;\u003dM\u0026lt;\u003d100), K(1\u0026lt;\u003dK\u0026lt;\u003d100) . The meaning is described above.\u003cbr\u003e Then N lines follow, each line contains 2 integers s\u003csub\u003ei\u003c/sub\u003e and t\u003csub\u003ei\u003c/sub\u003e(0 \u0026lt;\u003d s\u003csub\u003ei\u003c/sub\u003e \u0026lt; t\u003csub\u003ei\u003c/sub\u003e \u0026lt;100000).\u003cbr\u003e Then N lines follow, each line contains M integers, the j-th integer of the i-th line indicating C\u003csub\u003eij\u003c/sub\u003e(1\u0026lt;\u003dC\u003csub\u003eij\u003c/sub\u003e\u0026lt;\u003d100000) .\u003cbr\u003e Then N lines follow, each line contains M integers, the j-th integer of the i-th line indicating D\u003csub\u003eij\u003c/sub\u003e(1\u0026lt;\u003dD\u003csub\u003eij\u003c/sub\u003e\u0026lt;\u003d100000) .\u003cbr\u003e Then N lines follow, each line contains N integers, the i\u003csub\u003e2\u003c/sub\u003e-th integer of the i\u003csub\u003e1\u003c/sub\u003e-th line indicating E\u003csub\u003ei1i2\u003c/sub\u003e(1\u0026lt;\u003dE\u003csub\u003ei1j2\u003c/sub\u003e\u0026lt;\u003d100000) . \u003cbr\u003e Then N lines follow, each line contains N integers, the i\u003csub\u003e2\u003c/sub\u003e-th integer of the i\u003csub\u003e1\u003c/sub\u003e-th line indicating F\u003csub\u003ei1i2\u003c/sub\u003e(1 \u0026lt;\u003d F\u003csub\u003ei1j2\u003c/sub\u003e\u0026lt;\u003d100000) . \u003cbr\u003e Since the same candy will only be produced once, E\u003csub\u003eii\u003c/sub\u003e and F\u003csub\u003eii\u003c/sub\u003e are meaningless and will always be -1.\u003cbr\u003e The input ends by N\u003d0 M\u003d0 K\u003d0. Cases are separated with a blank line."}},{"title":"Output","value":{"format":"HTML","content":"\u0026nbsp;\u0026nbsp;For each test case, if all of M candies can be produced, output the sum of minimum producing cost in a single line. Otherwise output -1.\u003cbr\u003e"}},{"title":"Sample","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 2 1\r\n4 7\r\n2 4\r\n8 9\r\n4 4\r\n3 3\r\n3 3\r\n2 8\r\n12 3\r\n14 6\r\n-1 1 1\r\n1 -1 1\r\n1 1 -1\r\n-1 5 5\r\n5 -1 5\r\n5 5 -1\r\n\r\n1 1 2\r\n1 5\r\n5\r\n5\r\n-1\r\n-1\r\n\r\n0 0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11\r\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eFor the first example, the answer can be achieved in the following way:\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/d463fd3f0882d803cc25aea62c05a344?v\u003d1715575574\"\u003e\u003c/center\u003e \u003cbr\u003e\u0026nbsp;\u0026nbsp;In the picture, S i represents setting up time for candy i, A i represents changing time for candy i and P i represents producing time for candy i .\u003cbr\u003e\u0026nbsp;\u0026nbsp;So the total cost includes: \u003cbr\u003e setting up machine 1 for candy 1, costs 2\u003cbr\u003e setting up machine 2 for candy 2, costs 3\u003cbr\u003e changing state from candy 2 to candy 3, costs 5\u003cbr\u003e late start of candy 2, costs 1 \u003cbr\u003e"}}]}