4721: NOIP-J2009 T4：道路游戏
[Creator : ]
Description
小新正在玩一个简单的电脑游戏。
游戏中有一条环形马路，马路上有 nnn 个机器人工厂，两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这 nnn 个机器人工厂编号为 1−n1-n1−n ，因为马路是环形的，所以第 nnn 个机器人工厂和第 111 个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这 nnn 段马路也编号为 1−n1-n1−n ，并规定第 iii 段马路连接第 iii 个机器人工厂和第 i+1i+1i+1 个机器人工厂（ 1≤i≤n−11 \le i \le n-11≤i≤n−1 ），第 nnn 段马路连接第 nnn 个机器人工厂和第 111个机器人工厂。
游戏过程中，每个单位时间内，每段马路上都会出现一些金币，金币的数量会随着时间发生变化，即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买，机器人一旦被购买，便会沿着环形马路按顺时针方向一直行走，在每个单位时间内行走一次，即从当前所在的机器人工厂到达相邻的下一个机器人工厂，并将经过的马路上的所有金币收集给小新，例如，小新在 iii (1≤i≤n)(1 \le i \le n )(1≤i≤n) 号机器人工厂购买了一个机器人，这个机器人会从 iii 号机器人工厂开始，顺时针在马路上行走，第一次行走会经过 iii 号马路，到达 i+1i+1i+1 号机器人工厂（如果 i=ni=ni=n ，机器人会到达第 111 个机器人工厂），并将 iii 号马路上的所有金币收集给小新。 游戏中，环形马路上不能同时存在 222 个或者 222 个以上的机器人，并且每个机器人最多能够在环形马路上行走 ppp 次。小新购买机器人的同时，需要给这个机器人设定行走次数，行走次数可以为 1∼p1 \sim p1∼p 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失，小新必须立刻在任意一个机器人工厂中购买一个新的机器人，并给新的机器人设定新的行走次数。
以下是游戏的一些补充说明：
游戏中有一条环形马路，马路上有 nnn 个机器人工厂，两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这 nnn 个机器人工厂编号为 1−n1-n1−n ，因为马路是环形的，所以第 nnn 个机器人工厂和第 111 个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这 nnn 段马路也编号为 1−n1-n1−n ，并规定第 iii 段马路连接第 iii 个机器人工厂和第 i+1i+1i+1 个机器人工厂（ 1≤i≤n−11 \le i \le n-11≤i≤n−1 ），第 nnn 段马路连接第 nnn 个机器人工厂和第 111个机器人工厂。
游戏过程中，每个单位时间内，每段马路上都会出现一些金币，金币的数量会随着时间发生变化，即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买，机器人一旦被购买，便会沿着环形马路按顺时针方向一直行走，在每个单位时间内行走一次，即从当前所在的机器人工厂到达相邻的下一个机器人工厂，并将经过的马路上的所有金币收集给小新，例如，小新在 iii (1≤i≤n)(1 \le i \le n )(1≤i≤n) 号机器人工厂购买了一个机器人，这个机器人会从 iii 号机器人工厂开始，顺时针在马路上行走，第一次行走会经过 iii 号马路，到达 i+1i+1i+1 号机器人工厂（如果 i=ni=ni=n ，机器人会到达第 111 个机器人工厂），并将 iii 号马路上的所有金币收集给小新。 游戏中，环形马路上不能同时存在 222 个或者 222 个以上的机器人，并且每个机器人最多能够在环形马路上行走 ppp 次。小新购买机器人的同时，需要给这个机器人设定行走次数，行走次数可以为 1∼p1 \sim p1∼p 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失，小新必须立刻在任意一个机器人工厂中购买一个新的机器人，并给新的机器人设定新的行走次数。
以下是游戏的一些补充说明：
- 游戏从小新第一次购买机器人开始计时。
- 购买机器人和设定机器人的行走次数是瞬间完成的，不需要花费时间。
- 购买机器人和机器人行走是两个独立的过程，机器人行走时不能购买机器人，购买完机器人并且设定机器人行走次数之后机器人才能行走。
- 在同一个机器人工厂购买机器人的花费是相同的，但是在不同机器人工厂购买机器人的花费不一定相同。
- 购买机器人花费的金币，在游戏结束时再从小新收集的金币中扣除，所以在游戏过程中小新不用担心因金币不足，无法购买机器人而导致游戏无法进行。也因为如此，游戏结束后，收集的金币数量可能为负。
Input
第一行 333 个正整数 n,m,pn,m,pn,m,p 意义如题目所述。
接下来的 nnn 行，每行有 mmm 个正整数，每两个整数之间用一个空格隔开，其中第 iii 行描述了 iii 号马路上每个单位时间内出现的金币数量（ 1≤1 \le1≤ 金币数量 ≤100\le 100≤100 ），即第 iii 行的第 jjj（ 1≤j≤m1 \le j \le m1≤j≤m ）个数表示第 jjj 个单位时间内 iii 号马路上出现的金币数量。
最后一行，有 nnn 个整数，每两个整数之间用一个空格隔开，其中第 iii 个数表示在 iii 号机器人工厂购买机器人需要花费的金币数量（ 1≤1\le1≤ 金币数量 ≤100\le 100≤100 ）。
接下来的 nnn 行，每行有 mmm 个正整数，每两个整数之间用一个空格隔开，其中第 iii 行描述了 iii 号马路上每个单位时间内出现的金币数量（ 1≤1 \le1≤ 金币数量 ≤100\le 100≤100 ），即第 iii 行的第 jjj（ 1≤j≤m1 \le j \le m1≤j≤m ）个数表示第 jjj 个单位时间内 iii 号马路上出现的金币数量。
最后一行，有 nnn 个整数，每两个整数之间用一个空格隔开，其中第 iii 个数表示在 iii 号机器人工厂购买机器人需要花费的金币数量（ 1≤1\le1≤ 金币数量 ≤100\le 100≤100 ）。
Output
共一行，包含 111 个整数，表示在 mmm 个单位时间内，扣除购买机器人花费的金币之后，小新最多能收集到多少金币。
Sample 1 Input
2 3 2
1 2 3
2 3 4
1 2
Sample 1 Output
5