1837: 道路扩容

C城市的交通质量已经达到了令人难以忍受的地步。但是政府不打算增加过多的资金来建设高架公路或者立交桥。他们计划以有限的资金，对现在的交通网络进行扩容。

作为整项计划的一个子任务，政府的技术部门正在研究对以下给出的这种交通网络进行扩容的方案。

交通网络以邻接矩阵A _n×n形式给出：

若A _{i ,  j}不为0则表示路口i 到路口j之间的公路（道路均为单向）所能承载的最大车流量，这条公路上的实际车流量不能超过A_i，j。

若A_i，j为0则表示路口i到路口j之间没有公路。

路口1是整个网络的发点。即所有的车辆从这里进入网络；

路口n是整个网络的收点。也就是说，所有车辆从这里离开网络；

如果不出现交通堵塞，则在除1和n外的任意一个路口V，进入V的所有公路上的实际车流量总和应该等于离开V的所有公路上的实际车流量总和。

在保证无交通堵塞时，进入网络的总车流量存在一个最大值。例如左上图的交通网络（边上的数字表示能承受的最大车流量），进入网络的总车流量最大为40（此时每一条边上的实际流量如右上图所示）。如果要增加这个最大值，就要对现有的某些车流量已经饱和的公路进行扩容。

工程部门已经分析了对每条公路扩容的代价，并给出了邻接矩阵B _n×n。其中B _{i , j}表示使路口i到路口j之间公路可承载的最大车流量增加一个单位时，所需消耗的资金（如果i，j之间原本就没有公路则B_i，j=0）。

[任务]：

现在，请编程求出一个方案，表明对哪些公路进行扩容，分别进行多大的扩容，将使进入交通网络的总车流量的最大值增加k个单位（当然，不能出现交通堵塞），同时消耗的资金最少。

输入数据的第一行为两个整数n 和k（用空格分隔开）。(n≤50;k≤100)

接下来的n行数据是一个n*n的矩阵A _n×n，两个数之间以空格分隔开。

(0≤A_i，j≤100)

接下来的n行数据是一个n*n的矩阵B _n×n，两个数之间以空格分隔开。

(0≤B_i，j≤100)

第一行为一个整数，消耗资金的最小值。

接下来的若干行表示具体的扩容方案。每一行是关于一条道路的扩容情况（只输出扩容的道路），由三个整数组成（两两之间用空格分隔）。格式如下：

道路的起始路口i     道路的终止路口j      扩容后增加多少单位的车流量

5 20
0   30   20    0     0
0     0     0  20     0
0     0     0  30     0
0     0     0    0   50
0     0     0    0     0
0   20   10    0     0
0     0     0  10     0
0     0     0  20     0
0     0     0    0   50
0     0     0    0     0

700
1 3 10
2 4 10
4 5 10