{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eLily runs a repairing company that services the \u003ci\u003eQ\u003c/i\u003e blocks in the city. One day the company receives \u003ci\u003eM\u003c/i\u003e repair tasks, the \u003ci\u003ei\u003c/i\u003eth of which occurs in block \u003ci\u003ep\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, has a deadline \u003ci\u003et\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e on any repairman’s arrival, which is also its starting time, and takes a single repairman \u003ci\u003ed\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e time to finish. Repairmen work alone on all tasks and must finish one task before moving on to another. With a map of the city in hand, Lily want to know the minimum number of repairmen that have to be assign to this day’s tasks.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eThe input contains multiple test cases. Each test case begins with a line containing \u003ci\u003eQ\u003c/i\u003e and \u003ci\u003eM\u003c/i\u003e (0 \u0026lt; \u003ci\u003eQ\u003c/i\u003e ≤ 20, 0 \u0026lt; \u003ci\u003eM\u003c/i\u003e ≤ 200). Then follow \u003ci\u003eQ\u003c/i\u003e lines each with \u003ci\u003eQ\u003c/i\u003e integers, which represent a \u003ci\u003eQ\u003c/i\u003e × \u003ci\u003eQ\u003c/i\u003e matrix Δ \u003d {δ\u003ci\u003e\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e}, where δ\u003ci\u003e\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e means a bidirectional road connects the \u003ci\u003ei\u003c/i\u003eth and the \u003ci\u003ej\u003c/i\u003eth blocks and requires δ\u003ci\u003e\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e time to go from one end to another. If δ\u003ci\u003e\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e \u003d −1, such a road does not exist. The matrix is symmetric and all its diagonal elements are zeroes. Right below the matrix are \u003ci\u003eM\u003c/i\u003e lines describing the repairing tasks. The \u003ci\u003ei\u003c/i\u003eth of these lines contains \u003ci\u003ep\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003et\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e and \u003ci\u003ed\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e. Two zeroes on a separate line come after the last test case.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case output one line containing the minimum number of repairmen that have to be assigned.\u003c/p\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\u003e1 2\r\n0\r\n1 1 10\r\n1 5 10\r\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}