D. 电子钱包

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

很不幸,Chaneka 的钱包一块钱都不剩了!为了赚钱,他看上了 支股票以及这些股票未来 天的价格。设第 支股票第 天的价格为

Chaneka 有一项魔法:他可以将某个价格对应的数字记录下来,然后立刻获得等价值的电子币!不过,Chaneka 的这个魔法会受到某个给定参数 的影响。具体来说,他会使用恰好 次魔法,对于第 次魔法:

  1. Chaneka 会选择任意一支股票。假设他选择的是第 支股票;
  2. Chaneka 会选择一个正整数 ,要求
  3. Chaneka 会将 记录下来,然后立刻获得 电子币。之后, 会变为

Chaneka 想要知道:他一共最多能赚多少电子币?

输入格式

第一行三个正整数 ,含义见题面。

接下来输入 行,每一行 个正整数,表示

输出格式

输出一行一个整数,表示 Chaneka 最多能赚到的电子币。

样例

样例输入

3 3 1
10 4 2
8 1 9
4 8 2

样例输出

27

样例解释

Chaneka 会依次选择 ,一共能赚 电子币。

数据范围与提示

  • 对于 的数据,

  • 对于 的数据,

  • 对于另 的数据,

  • 对于 的数据,