Description

有一条环形路，路上有n个点，第i个点和第i+1个点有边相连（第n个点与第1个点有边相连）。每个点都可以花费 不同的代价生产一个机 器人，且机器人可以顺时针走不多于p步（每走一步消耗一单位时间），并捡起此时路上的 金币。最多只能有一个机器人存在于路上。不同的时间每条路上金币数不 同。求最后能够得到的最大金币数（即 捡起的金币数减去生产机器人需要的金币数）。

Format

Input

第一行3个正整数，n，m，p，意义如题目所述。 接下来的n行，每行有m个正整数，每两个整数之间用一个空格隔开， 其中第i行描述了i号马路上每个单位时间内出现的金币数量（1≤金币数量≤1000）， 即第i行的第j（1≤j≤m）个数表示第j个单位时间内i号马路上出现的金币数量。 最后一行，有n个整数，每两个整数之间用一个空格隔开， 其中第i个数表示在i号机器人工厂购买机器人需要花费的金币数量（1≤金币数量≤1000）。

Output

包含 1 个整数，表示在 m 个单位时间内，扣除购买机器人花费的金币之后，小新最多能收集到多少金币。

Samples

2 3 2 
1 2 3 
2 3 4 
1 2 

5