Description

每台计算机都由$P$个零件组成。

当所有这些零件都存在时，计算机就组装好了。

有$N$台不同的机器组装计算机。

每台机器都从半成品计算机上删除或添加一些零件。

输入规范描述了在半成品计算机中必须包含哪些零件。

规范是一组$P$个数字$0$、$1$或$2$，其中$0$表示不需要该零件，$1$表示需要该零件，$2$表示无所谓。

输出规范描述了操作结果，是一组$P$个数字$0$或$1$，其中$0$表示该零件不存在，$1$表示该零件存在。

求解如何重新安排生产线可获得最大的整体性能。

Format

Input

输入文件包含整数$P$、$N$，然后是机器的$N$个描述。

对第$i$台机器的描述用$2$$P$+$1$整数$Q_i$$S_{i,1}$$S_{i,2}$…$S_{i,P}$$D_{i,1}$$D_{i,2}$…$D_{i,P}$表示，其中$Q_i$表示单位时间的产能，$S_{i,j}$表示第$j$部分的输入规范，$D_{i,k}$表示第$k$部分的输出规范。

$1$$≤$$P$$≤$$1$$0$，$1$$≤$$N$$≤$$5$$0$，$1$$≤$$Q_i$$≤$$1$$0$$0$$0$$0$。

Output

输出可能的最大整体性能，然后是$M$$（$必须建立的连接数$）$，接着是$M$个连接描述。

对机器$A$和机器$B$之间的每个连接都必须用$3$个正数以“$A$ $B$ $W$”形式描述，其中$W$是每小时从机器$A$传送到机器$B$的计算机数量。

若存在多个解决方案，则输出其中任意一个。

Samples

3 4
15 0 0 0  0 1 0
10 0 0 0  0 1 1
30 0 1 2  1 1 1
3 0 2 1  1 1 1
3 5
5 0 0 0  0 1 0
100 0 1 0  1 0 1
3 0 1 0  1 1 0
1 1 0 1  1 1 0
300 1 1 2  1 1 1
2 2
100 0 0 1 0
200 0 1 1 1

25 2
1 3 15
2 3 10

4 5
1 3 3 
3 5 3
1 2 1
2 4 1
4 5 1


00

来源

POJ3436