不是因为题目太长（nan），而是因为题目太难（chang）
小新正在玩一个简单的电脑游戏。 游戏中有一条环形马路，马路上有 n 个机器人工厂，两个相邻机器人工厂之间由一小段 马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这 n 个机器人工厂编号为 1~n，因为马路是环形的，所以第 n 个机器人工厂和第 1 个机器人工厂是由一段马路连接在 一起的。小新将连接机器人工厂的这 n 段马路也编号为 1~n，并规定第 i 段马路连接第 i 个 机器人工厂和第 i+1 个机器人工厂（ 1≤ i≤ n-1），第 n 段马路连接第 n 个机器人工厂和第 1 个机器人工厂。 游戏过程中，每个单位时间内，每段马路上都会出现一些金币，金币的数量会随着时间 发生变化，即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人 的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买，机器 人一旦被购买，便会沿着环形马路按顺时针方向一直行走，在每个单位时间内行走一次，即 从当前所在的机器人工厂到达相邻的下一个机器人工厂， 并将经过的马路上的所有金币收集 给小新，例如，小新在 i（ 1≤ i≤ n）号机器人工厂购买了一个机器人，这个机器人会从 i 号 机器人工厂开始，顺时针在马路上行走，第一次行走会经过 i 号马路，到达 i+1 号机器人工 厂（如果 i=n，机器人会到达第 1 个机器人工厂），并将 i 号马路上的所有金币收集给小新。 游戏中，环形马路上不能同时存在 2 个或者 2 个以上的机器人，并且每个机器人最多能 够在环形马路上行走 p 次。小新购买机器人的同时，需要给这个机器人设定行走次数，行走 次数可以为 1~p 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失，小 新必须立刻在任意一个机器人工厂中购买一个新的机器人， 并给新的机器人设定新的行走次 数。 以下是游戏的一些补充说明：
- 游戏从小新第一次购买机器人开始计时。
- 购买机器人和设定机器人的行走次数是瞬间完成的，不需要花费时间。
- 购买机器人和机器人行走是两个独立的过程，机器人行走时不能购买机器人，购买 完机器人并且设定机器人行走次数之后机器人才能行走。
- 在同一个机器人工厂购买机器人的花费是相同的，但是在不同机器人工厂购买机器 人的花费不一定相同。
- 购买机器人花费的金币，在游戏结束时再从小新收集的金币中扣除，所以在游戏过 程中小新不用担心因金币不足， 无法购买机器人而导致游戏无法进行。 也因为如此， 游戏结束后，收集的金币数量可能为负。 现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人 需要的花费，请你告诉小新，经过 m 个单位时间后，扣除购买机器人的花费，小新最多能 收集到多少金币。
输入格式
第一行 3 个正整数， n， m， p，意义如题目所述。 接下来的 n 行，每行有 m 个正整数，每两个整数之间用一个空格隔开，其中第 i 行描 述了 i 号马路上每个单位时间内出现的金币数量（ 1 ≤ 金币数量 ≤ 100），即第 i 行的第 j （ 1≤ j≤ m）个数表示第 j 个单位时间内 i 号马路上出现的金币数量。 最后一行，有 n 个整数，每两个整数之间用一个空格隔开，其中第 i 个数表示在 i 号机 器人工厂购买机器人需要花费的金币数量（ 1≤ 金币数量≤ 100）。
【数据范围】 对于 40%的数据， 2≤ n≤ 40， 1≤ m ≤ 40。 对于 90%的数据， 2≤ n≤ 200， 1≤ m ≤ 200。 对于 100%的数据， 2≤ n≤ 1000， 1≤ m≤ 1000， 1≤ p≤ m。
输出格式
共一行，包含 1 个整数，表示在 m 个单位时间内，扣除购买机器人 花费的金币之后，小新最多能收集到多少金币。
你跳过华尔兹吗？当音乐响起，当你随着旋律滑动舞步，是不是有一种漫步 仙境的惬意？众所周知，跳华尔兹时，最重要的是有好的音乐。但是很少有几个人知道， 世界上最伟大的钢琴家一生都漂泊在大海上，他的名字叫丹尼·布德曼·T.D.·柠 檬·1900，朋友们都叫他1900。
1900在20世纪的第一年出生在往返于欧美的邮轮弗吉尼亚号上。很不幸， 他刚出生就被抛弃，成了孤儿。1900 孤独的成长在弗吉尼亚号上，从未离开过 这个摇晃的世界。也许是对他命运的补偿，上帝派可爱的小天使艾米丽照顾他。 可能是天使的点化，1900拥有不可思议的钢琴天赋：从未有人教，从没看过 乐谱，但他却能凭着自己的感觉弹出最沁人心脾的旋律。当1900的音乐获得邮 轮上所有人的欢迎时，他才8岁，而此时，他已经乘着海轮往返欧美大陆50余 次了。
虽说是钢琴奇才，但1900还是个孩子，他有着和一般男孩一样的好奇和调皮， 只不过更多一层浪漫的色彩罢了： 这是一个风雨交加的夜晚，海风卷起层层巨浪拍打着弗吉尼亚号，邮轮随着 巨浪剧烈的摇摆。船上的新萨克斯手迈克斯·托尼晕船了，1900招呼托尼和他 一起坐到舞厅里的钢琴上，然后松开了固定钢琴的闸，于是，钢琴随着海轮的倾 斜滑动起来。准确的说，我们的主角1900、钢琴、邮轮随着1900的旋律一起跳 起了华尔兹，随着“嘣嚓嚓”的节奏，托尼的晕船症也奇迹般的消失了。后来托 尼在回忆录上这样写道： 大海摇晃着我们 使我们转来转去 快速的掠过灯和家具 我意识到我们正在和大海一起跳舞 真是完美而疯狂的舞者 晚上在金色的地板上快乐的跳着华尔兹是不是很惬意呢？也许，我们忘记了 一个人，那就是艾米丽，她可没闲着：她必须在适当的时候施展魔法帮助1900， 不让钢琴碰上舞厅里的家具。
不妨认为舞厅是一个N行M列的矩阵，矩阵中的某些方格上堆放了一些家具， 其他的则是空地。钢琴可以在空地上滑动，但不能撞上家具或滑出舞厅，否则会 损坏钢琴和家具，引来难缠的船长。 每个时刻，钢琴都会随着船体倾斜的方向向相邻的方格滑动一格，相邻的方 格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法：如 果不施魔法，则钢琴会滑动；如果施魔法，则钢琴会原地不动。 艾米丽是个天使，她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里 滑行的路程尽量长，这样1900会非常高兴，同时也有利于治疗托尼的晕船。但 艾米丽还太小，不会算，所以希望你能帮助她。
跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。 跳房子的游戏规则如下： 在地面上确定一个起点，然后在起点右侧画 n 个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个格子能得到的分数。玩家第一次从起点开始向 右跳， 跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定： 玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。 现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 d。小 R 希望改进他的机器人，如果他花 g 个金 币改进他的机器人，那么他的机器人灵活性就能增加 g， 但是需要注意的是，每次弹跳的距离至少为 1。 具体而言， 当g < d时， 他的机器人每次可以选择向右弹跳的距离为 d-g, d-g+1, d-g+2， …， d+g-2， d+g-1， d+g； 否则（当g ≥ d时），他的机器人每次可以选择向右弹跳的距离为 1， 2， 3， …， d+g-2， d+g-1， d+g。 现在小 R 希望获得至少 k 分，请问他至少要花多少金币来改造他的机器人。
输入格式
第一行三个正整数 n， d， k， 分别表示格子的数目， 改进前机器人弹跳的固定距离， 以及希望至少获得的分数。 相邻两个数之间用一个空格隔开。 接下来 n 行，每行两个正整数Xi,Si，分别表示起点到第i个格子的距离以及第i个格子的分数。 两个数之间用一个空格隔开。 保证Xi按递增顺序输入。
【数据规模与约定】 本题共 10 组测试数据，每组数据 10 分。对于全部的数据满足1 ≤ n ≤ 500000, 1 ≤ d ≤ 2000, 1 ≤ Xi, k ≤ 10^9, |si| < 10^5。 对于第 1， 2 组测试数据， n ≤ 10； 对于第 3， 4， 5 组测试数据， n ≤ 500 对于第 6， 7， 8 组测试数据， d = 1
输出格式
共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 k 分，输出-1。