逛逛集市，兑兑奖品，看看节目对农夫约翰来说不算什么，可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市，他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛集市，约翰准备让奶牛们在集市上以车代步。但是，约翰木有钱，他租来的班车只能在集市上沿直线跑一次，而且只能停靠N个地点（所有地点都以1到N之间的一个数字来表示）。 现在奶牛们分成K个小组，第i组有 ()头奶牛，他们希望从跑到 ()。由于班车容量有限，可能载不下所有想乘车的奶牛们，此时也允许小组里的一部分奶牛分开乘坐班车。约翰经过调查得知班车的容量是C ，请你帮助约翰计划一个尽可能满足更多奶牛愿望的方案。

输入描述:

第一行包括三个整数K N C，彼此用空格隔开。第二行到K+1行：在第i+1行，将会告诉你第i组奶牛的信息：和，彼此用空格隔开。

输出描述:

可以坐班车的奶牛的最大头数。

备注:

。