{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"生产电脑的工厂将一台电脑分成 $P$ 个部件来进行流水线生产组装。有 $N$ 个生产车间,每个车间可以将一个半成品电脑添加某些部件,使之成为另一个半成品电脑或者成为一台完好的电脑。每个车间有一个效率 $K$ (即在单位时间内可以将 $K$ 个半成品组装为另外 $K$ 个半成品或者完好的电脑)。每个车间在组装完成之后,都将组装后的半成品送到另外一个车间,成品直接送到成品区。 \n\n\n 对于每个车间,有输入口和输出口。每个口有 $P$ 个部件表示,每个部件使用 $0$, $1$ 或 $2$ 来表示状态:$1$ 表示一定需要有入/出的材料,$0$ 表示不能有入/出的材料,$2$ 表示可能有入的材料。如果一个机器输入口的 $P$ 个部件全是 $0$ ,代表是起始机器;如果一个机器输出口全是 $1$ ,那么代表电脑加工完成。\n\n求这个工厂单位时间内最多可以产出多少台电脑。"}},{"title":"Input","value":{"format":"MD","content":"第一行,输入两个数 $P$ , $N$ ,表示一台电脑分成 $P$ 个部件,有 $N$ 个生产车间。\n接下来 $N$ 行,每行有 $(2P+1)$ 个数字。第一个数字 $Q$ 代表当前车间每\\单位时间最多能加工 $Q$ 个部件。接下来 $P$ 个数字代表加工入口时部件需要的状态,再往后的 $P$ 个数字代表加工出口后部件的状态。\n\u003cp\u003e1 ≤ \u003ci\u003eP\u003c/i\u003e ≤ 10, 1 ≤ \u003ci\u003eN \u003c/i\u003e≤ 50, 1 ≤ \u003ci\u003eQ\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ 10000 \u003c/p\u003e"}},{"title":"Output","value":{"format":"MD","content":"输出单位时间内,最多能造的成品电脑数量,并输出方案。\n\n第一行输出 $2$ 个数,分别为单位时间内最多能造的电脑数量,以及输出工厂之间的连接数量 $M$ 。\n接下来 $M$ 行,输出连接的两个工厂编号,以及传输的部件台数。\n\n如果有多种解决方案,输出其一即可。"}},{"title":"Sample Input","value":{"format":"MD","content":"\u003cpre class\u003d\"sio\"\u003e\u003cb\u003eSample input 1\u003c/b\u003e\n3 4\n15 0 0 0 0 1 0\n10 0 0 0 0 1 1\n30 0 1 2 1 1 1\n3 0 2 1 1 1 1\n\u003cb\u003eSample input 2\u003c/b\u003e\n3 5\n5 0 0 0 0 1 0\n100 0 1 0 1 0 1\n3 0 1 0 1 1 0\n1 1 0 1 1 1 0\n300 1 1 2 1 1 1\n\u003cb\u003eSample input 3\u003c/b\u003e\n2 2\n100 0 0 1 0\n200 0 1 1 1\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"MD","content":"\u003cpre class\u003d\"sio\"\u003e\u003cb\u003eSample output 1\u003c/b\u003e\n25 2\n1 3 15\n2 3 10\n\u003cb\u003eSample output 2\u003c/b\u003e\n4 5\n1 3 3\n3 5 3\n1 2 1\n2 4 1\n4 5 1\n\u003cb\u003eSample output 3\u003c/b\u003e\n0 0\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"MD","content":"第一个样例最多生产25台,第一个车间生产15台给第三车间,第二个车间生产10台给第三车间,第三车间拿25台生产成品。\n\n第二个样例最多生产4台,第一个车间生产3台给第三车间,第三车间加工3台给第五车间,第一车间生产1台给第二车间,第二车间加工1台给第四车间,第四车间加工1台给第五车间,第五车间拿4台加工出成品。"}}]}