Problem: There are N panels arranged in a row in Takahashi's house, numbered 1 through N. The i-th panel has a number A_i written on it. Takahashi is playing by throwing balls at these panels.

Takahashi threw a ball K times. Let the panel hit by a boll in the i-th throw be panel p_i. He set the score for the i-th throw as i \times A_{p_i}.

He was about to calculate the total score for his throws, when he realized that he forgot the panels hit by balls, p_1,p_2,...,p_K. The only fact he remembers is that for every i (1 ≦ i ≦ K-1), 1 ≦ p_{i+1}-p_i ≦ M holds. Based on this fact, find the maximum possible total score for his throws.

Constraints

* 1 ≦ M ≦ N ≦ 100,000
* 1 ≦ K ≦ min(300,N)
* 1 ≦ A_i ≦ 10^{9}

Input

The input is given from Standard Input in the following format:


N M K
A_1 A_2 … A_N


Output

Print the maximum possible total score for Takahashi's throws.

Examples

Input

5 2 3
10 2 8 10 2


Output

56


Input

5 5 2
5 2 10 5 9


Output

28


Input

10 3 5
3 7 2 6 9 4 8 5 1 1000000000


Output

5000000078

Solution (in CPP):

Solution:
    #include <bits/stdc++.h>
    using namespace std;
         
    typedef vector<int> VI;
    typedef vector<VI> VVI;
    typedef vector<string> VS;
    typedef pair<int, int> PII;
    typedef long long LL;
    typedef pair<LL, LL> PLL;
         
    #define ALL(a)  (a).begin(),(a).end()
    #define RALL(a) (a).rbegin(), (a).rend()
    #define PB push_back
    #define EB emplace_back
    #define MP make_pair
    #define SZ(a) int((a).size())
    #define SORT(c) sort((c).begin(),(c).end())
         
    #define FOR(i,a,b) for(int i=(a);i<(b);++i)
    #define REP(i,n)  FOR(i,0,n)
         
    #define FF first
    #define SS second
    template<class S, class T>
    istream& operator>>(istream& is, pair<S,T>& p){
      return is >> p.FF >> p.SS;
    }
         
    const double EPS = 1e-10;
    const double PI  = acos(-1.0);
    const LL MOD = 1e9+7;
         
         
    LL dp[310][100010];
    LL mx[310][100010];
     
    // 幅Wの窓で値pを追加した時の最大値
    void add(deque<PLL>& dq, PLL p, int W){
      while(!dq.empty() && dq.back().FF < p.FF)
    	dq.pop_back();
      dq.push_back(p);
      while(!dq.empty() && p.SS - dq.front().SS + 1 > W)
    	dq.pop_front();
    }
     
    int main(){
      cin.tie(0);
      ios_base::sync_with_stdio(false);
         
      LL N, M, K; cin >> N >> M >> K;
      vector<LL> xs(N);
      REP(i,N) cin >> xs[i];
      deque<PLL> dq;
      REP(i,N){
    	dp[1][i] = xs[i];
    	add(dq, MP(dp[1][i],i), M);
    	mx[1][i] = dq.front().FF;
      }
     
      for(LL i=2;i<=K;++i){
    	dq.clear();
    	for(int j=i-1;j<N;++j){
    	  LL nxt = mx[i-1][j-1] + i * xs[j];
    	  dp[i][j] = max(dp[i][j], nxt);
     
    	  add(dq, MP(dp[i][j],j), M);
    	  mx[i][j] = dq.front().FF;
    	}
      }

      LL ans = 0;
      REP(i,N) ans = max(ans, dp[K][i]);
      cout << ans << endl;
          
      return 0;
    }