描述

经过数周的期待，比赛终于正式开始。

不过天公不作美，今天的天气十分诡异，一会儿下雨，一会儿刮风。要知道，天气的变化对F1比赛的影响是巨大的，恶劣的天气甚至会严重干扰赛车手发挥。因此，各车队的总指挥都会在赛前根据赛道环境和天气的变化为车手制定一系列周密的计划。幸运的是，F1专用气象站拥有最顶尖的技术，能够精确测量出每一圈的天气情况，这大大降低了计划的风险。

在计划中，对轮胎的正确选择是至关重要的。每一场比赛，赛会都会提供给各赛车不同总类的轮胎（每种轮胎数量不限）。出发时，各赛车可根据需要使用任意一种轮胎。以后每过一圈，赛车可以选择不更换轮胎继续前进，或者进维修站更换任一种轮胎，但需要消耗一定的换胎时间。

通过测试，换胎时间和各种轮胎在各圈所消耗的单圈时间已精确测出，你能帮车队求出完成比赛的最短时间么？

格式

输入格式

第一行是三个整数n，m，c（1<=n<=1000，1<=m<=1000，1<=c<=1000000），分别表示总圈数，轮胎种类数和换胎时间。接下来n行，每行m个整数，第i行第j个是tij（1<=tij<=1000000），表示在第i圈时第j种轮胎所消耗的单圈时间。

输出格式

一个整数s，表示最短的总时间。

样例1

样例输入1

【样例输入】

4 3 30
50 60 100
70 50 100
10 50 90
100 30 10

样例输出1

【样例输出】

170

限制

各个测试点1s

提示

30%的数据满足n<=15，m<=2