{"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\u003eAfter the end of the truck drivers\u0027 strike, you and the rest of Nlogônia logistics specialists now have the task of planning the refueling of the gas stations in the city. For this, we collected information on stocks of $$$R$$$ refineries and about the demands of $$$P$$$ gas stations. In addition, there are contractual restrictions that some refineries cannot supply some gas stations; When a refinery can provide a station, the shorter route to transport fuel from one place to another is known.\u003c/p\u003e\u003cp\u003eThe experts\u0027 task is to minimize the time all stations are supplied, satisfying their demands. The refineries have a sufficiently large amount of trucks, so that you can assume that each truck will need to make only one trip from a refinery to a gas station. The capacity of each truck is greater than the demand of any gas station, but it may be necessary to use more than one refinery.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains three integers $$$P, R, C$$$, respectively the number of gas stations, the number of refineries and the number of pairs of refineries and gas stations whose time will be given ($$$1 \\leq P, R \\leq 1000$$$; $$$1 \\leq C \\leq 20000$$$). The second line contains $$$P$$$ integers $$$D_i$$$ ($$$1 \\leq D_i \\leq 10^4$$$), representing the demands in liters of gasoline of the gas stations $$$i \u003d 1, 2, \\dots, P$$$, in that order. The third line contains $$$R$$$ integers $$$E_i$$$ ($$$1 \\leq E_i \\leq 10^4$$$), representing stocks, in liters of gasoline, of refineries $$$i \u003d 1, 2, \\dots, R$$$, in that order. Finally, the latest $$$C$$$ lines describe course times, in minutes, between stations and refineries. Each of these rows contains three integers, $$$I, J, T$$$ ($$$1 \\leq I \\leq P$$$; $$$1 \\leq J \\leq R$$$; $$$1 \\leq T \\leq 10^6$$$), where $$$I$$$ is the ID of a post, $$$J$$$ is the ID of a refinery and $$$T$$$ is the time in the course of a refinery truck $$$J$$$ to $$$I$$$. No pair $$$(J, I)$$$ repeats. Not all pairs are informed; If a pair is not informed, contractual restrictions prevents the refinery from supplying the station.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint an integer that indicates the minimum time in minutes for all stations to be completely filled up. If this is not possible, print \u003cspan class\u003d\"tex-font-style-tt\"\u003e−1\u003c/span\u003e.\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\u003e3 2 5\n20 10 10\n30 20\n1 1 2\n2 1 1\n2 2 3\n3 1 4\n3 2 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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 2 5\n20 10 10\n25 30\n1 1 3\n2 1 1\n2 2 4\n3 1 2\n3 2 5\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"}},{"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 3 9\n10 10 10 20\n10 15 30\n1 1 1\n1 2 1\n2 1 3\n2 2 2\n3 1 10\n3 2 10\n4 1 1\n4 2 2\n4 3 30\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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\u003e1 2 2\n40\n30 10\n1 1 100\n1 2 200\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e200\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}