Problem 1535. -- NOIP2009普及组 道路游戏

1535: NOIP2009普及组 道路游戏

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 16  Solved: 12
[Submit][Status][Web Board]

Description

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

Input

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

Output

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

Sample Input

2 3 2
1 2 3
2 3 4
1 2

Sample Output

5

HINT

Source

[Submit][Status]