背景

曹师傅家有一个神奇的能量线路,可以违反能量守恒定律地将少量能量转化为大量的能量.

描述

整个线路可以看作是一个n*m的矩阵,每个点有两种状态“充能”,“空白”.矩阵中的某些点一开始就是”充能”状态的.
定义一类叫做能量放大的操作:对于一种能量放大,当第X行的要求点为“充能”状态之后,且第X+1行的要求点为“空白”状态时.将第X行要求点转化为“空白”,将第X+1行的要求点转化为”充能”,并获取一定的能量增值.
能量线路的输出能量就是按行非递减顺序进行一定次数的放大操作之后能造成的能量增值的总值(一开始为0).而现在曹师傅需要求出这个线路最多能输出多少能量.

格式

输入格式

第1行,N,M
第2~N+1行, 矩阵的初始状态.0表示”空白”,1表示”充能”.
第N+2行,一个K,即能量放大的方案数
第N+3~第N+3*K+2行,输入K种方案,每种占3行,第一行是当前行的要求点,第二行是下一行的要求点,第三行是这种操作将获得的能量增值的大小.(两行的要求点都是”0”无要求,”1”为要求点).

输出格式

仅一行,即能获得的最大能量.

样例1

样例输入1

2 10
010101111
100000001
4
010100000
100000000
10
010101000
100100000   
20
000000110
000100000
30
000000010
000000000
40

样例输出1

40

限制

都是1S

提示

对于20%的数据: 1<=n<=10; 1<=m<=5; 1<=k<=5;
对于100%的数据: 1<=n<=128; 1<=m<=18; 1<=k<=20;

来源

YoungBoy From HNSDFZ
Welcome to www.nevergoby.cn