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>
#define ll long long
#define REP(i, n) for (ll i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (ll i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define fi first
#define se second
#define pb push_back
#define debug(x) cerr << #x << ": " << (x) << endl
#define debug2(x, y) cerr << #x << ": " << (x) << " " << #y << ": " << y << endl;
#define int long long
using namespace std;
using II = pair<int, int>;
using VII = vector<II>;
using VI = vector<int>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
template <class T = int> inline T in() { T x; cin >> x; return x; }
template <class T = int> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <class T = int> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
template <class T> ostream& operator<<(ostream &s, const vector<T>& d) { int n = d.size(); REP (i, n) s << d[i] << " "; return s; }
template <class T> ostream& operator<<(ostream &s, const vector<vector<T>>& dd) { for (vector<T> d: dd) s << d << endl; return s; }
struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); } } fast;
const int MOD = 1e9 + 7;

template <class T = int>
vector<T> slide_min(const vector<T>& a, int w, function<bool(T, T)> cmp = less<T>()) {
  int n = a.size();
  vector<T> ret(n);
  deque<int> dq;
  REP (i, n) {
    while (!dq.empty() && !cmp(a[dq.back()], a[i])) {
      dq.pop_back();
    }
    dq.push_back(i);
    while (dq.front() <= i - w) {
      dq.pop_front();
    }
    ret[i] = dq.front();
  }
  return ret;
}

signed main() {
  int N, M, K; cin >> N >> M >> K;
  VI A(N);
  REP (i, N) cin >> A[i];

  VVI dp(K + 1, VI(N + 1, 0));
  REPI (i, 1, K + 1) {
    dp[i][0] = -1;
  }
  VVI mas(K + 1, VI(N + 1));
  REPI (i, 1, K + 1) {
    REPI (j, 1, N + 1) {
      int prv = dp[i - 1][mas[i - 1][j - 1]];
      dp[i][j] = prv == -1 ? -1 : prv + i * A[j - 1];
    }
    // スライド最大値
    mas[i] = slide_min<int>(dp[i], M, greater<int>());
  }
  cout << *max_element(ALL(dp[K])) << endl;
}