#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<long long> dir_x{0ll, 0ll, -1ll, 1ll};
vector<long long> dir_y{1ll, -1ll, 0ll, 0ll};
long long power_mod(long long x, long long y, long long m) {
  long long arr = 1;
  x %= m;
  while (y) {
    if (y & 1) {
      arr = (arr * x) % m;
    }
    y >>= 1;
    x = (x * x) % m;
  }
  return arr;
}
long long power(long long x, long long y) {
  long long arr = 1;
  while (y) {
    if (y & 1) {
      arr *= x;
    }
    y >>= 1;
    x = x * x;
  }
  return arr;
}
long long mod_inv(long long x, long long m) { return power_mod(x, m - 2, m); }
int randomGenerator(int limit) {
  random_device rd;
  mt19937 gen(rd());
  uniform_int_distribution<> dis(1, limit);
  return dis(gen);
}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
bool comp(const pair<long long, pair<long long, long long>> &a,
          const pair<long long, pair<long long, long long>> &b) {
  if (a.first == b.first) {
    return (a.second < b.second);
  }
  return (a.first < b.first);
}
struct hash_pair {
  template <class T1, class T2>
  size_t operator()(const pair<T1, T2> &p) const {
    auto hash1 = hash<T1>{}(p.first);
    auto hash2 = hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};
bool isPalindrome(string s) {
  bool flag = true;
  for (int i = 0; i < s.length() / 2; i++) {
    if (s[i] != s[s.length() - i - 1]) {
      flag = false;
      break;
    }
  }
  return flag;
}
bool isPerfectSquare(long long n) {
  long double val = sqrt(n);
  return (val - floor(val) == 0);
}
bool isPrime(long long n) {
  if (n < 2) {
    return false;
  }
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}
long long NCR(long long n, long long k) {
  long long res = 1;
  if (k > n - k) {
    k = n - k;
  }
  for (long long i = 0; i < (k); i++) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
long long cntBits(long long n) {
  long long cnt = 0;
  for (long long i = 0; i < 64; i++) {
    if ((1ll << i) & n) {
      cnt++;
    }
  }
  return cnt;
}
long long n;
map<pair<pair<long long, long long>, pair<long long, long long>>, long long> dp;
vector<long long> arr(100005);
long long recur(long long i, long long k, long long z, long long p) {
  if (i == n) {
    return 0;
  }
  if (k == 0) {
    return arr[i];
  }
  pair<long long, long long> f = {i, k};
  pair<long long, long long> s = {z, p};
  pair<pair<long long, long long>, pair<long long, long long>> pp = {f, s};
  if (dp.find(pp) != dp.end()) {
    return dp[pp];
  } else if (i == n and z > 0 and p == 0) {
    dp[pp] = recur(i - 1, k - 1, z - 1, 1);
    return dp[pp];
  } else if (p == 1 or z == 0 or i == 0) {
    dp[pp] = arr[i] + recur(i + 1, k - 1, z, 0);
    return dp[pp];
  }
  dp[pp] =
      arr[i] + max(recur(i + 1, k - 1, z, 0), recur(i - 1, k - 1, z - 1, 1));
  return dp[pp];
}
void solve() {
  dp.clear();
  long long k, z;
  cin >> n >> k >> z;
  for (long long i = 0; i < (n); i++) {
    cin >> arr[i];
  }
  long long ans = recur(1, k - 1, z, 0);
  ans += arr[0];
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long t;
  cin >> t;
  for (long long i = (1); i <= (t); i++) {
    solve();
  }
  return 0;
}

### Prompt

Generate a cpp solution to the following problem:

You are given an array a_1, a_2, ..., a_n, consisting of n positive integers. 

Initially you are standing at index 1 and have a score equal to a_1. You can perform two kinds of moves: 

  1. move right — go from your current index x to x+1 and add a_{x+1} to your score. This move can only be performed if x<n. 
  2. move left — go from your current index x to x-1 and add a_{x-1} to your score. This move can only be performed if x>1. Also, you can't perform two or more moves to the left in a row.



You want to perform exactly k moves. Also, there should be no more than z moves to the left among them.

What is the maximum score you can achieve?

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of testcases.

The first line of each testcase contains three integers n, k and z (2 ≤ n ≤ 10^5, 1 ≤ k ≤ n - 1, 0 ≤ z ≤ min(5, k)) — the number of elements in the array, the total number of moves you should perform and the maximum number of moves to the left you can perform.

The second line of each testcase contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^4) — the given array.

The sum of n over all testcases does not exceed 3 ⋅ 10^5.

Output

Print t integers — for each testcase output the maximum score you can achieve if you make exactly k moves in total, no more than z of them are to the left and there are no two or more moves to the left in a row.

Example

Input


4
5 4 0
1 5 4 3 2
5 4 1
1 5 4 3 2
5 4 4
10 20 30 40 50
10 7 3
4 6 8 2 9 9 7 4 10 9


Output


15
19
150
56

Note

In the first testcase you are not allowed to move left at all. So you make four moves to the right and obtain the score a_1 + a_2 + a_3 + a_4 + a_5.

In the second example you can move one time to the left. So we can follow these moves: right, right, left, right. The score will be a_1 + a_2 + a_3 + a_2 + a_3.

In the third example you can move four times to the left but it's not optimal anyway, you can just move four times to the right and obtain the score a_1 + a_2 + a_3 + a_4 + a_5.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<long long> dir_x{0ll, 0ll, -1ll, 1ll};
vector<long long> dir_y{1ll, -1ll, 0ll, 0ll};
long long power_mod(long long x, long long y, long long m) {
  long long arr = 1;
  x %= m;
  while (y) {
    if (y & 1) {
      arr = (arr * x) % m;
    }
    y >>= 1;
    x = (x * x) % m;
  }
  return arr;
}
long long power(long long x, long long y) {
  long long arr = 1;
  while (y) {
    if (y & 1) {
      arr *= x;
    }
    y >>= 1;
    x = x * x;
  }
  return arr;
}
long long mod_inv(long long x, long long m) { return power_mod(x, m - 2, m); }
int randomGenerator(int limit) {
  random_device rd;
  mt19937 gen(rd());
  uniform_int_distribution<> dis(1, limit);
  return dis(gen);
}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
bool comp(const pair<long long, pair<long long, long long>> &a,
          const pair<long long, pair<long long, long long>> &b) {
  if (a.first == b.first) {
    return (a.second < b.second);
  }
  return (a.first < b.first);
}
struct hash_pair {
  template <class T1, class T2>
  size_t operator()(const pair<T1, T2> &p) const {
    auto hash1 = hash<T1>{}(p.first);
    auto hash2 = hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};
bool isPalindrome(string s) {
  bool flag = true;
  for (int i = 0; i < s.length() / 2; i++) {
    if (s[i] != s[s.length() - i - 1]) {
      flag = false;
      break;
    }
  }
  return flag;
}
bool isPerfectSquare(long long n) {
  long double val = sqrt(n);
  return (val - floor(val) == 0);
}
bool isPrime(long long n) {
  if (n < 2) {
    return false;
  }
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}
long long NCR(long long n, long long k) {
  long long res = 1;
  if (k > n - k) {
    k = n - k;
  }
  for (long long i = 0; i < (k); i++) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
long long cntBits(long long n) {
  long long cnt = 0;
  for (long long i = 0; i < 64; i++) {
    if ((1ll << i) & n) {
      cnt++;
    }
  }
  return cnt;
}
long long n;
map<pair<pair<long long, long long>, pair<long long, long long>>, long long> dp;
vector<long long> arr(100005);
long long recur(long long i, long long k, long long z, long long p) {
  if (i == n) {
    return 0;
  }
  if (k == 0) {
    return arr[i];
  }
  pair<long long, long long> f = {i, k};
  pair<long long, long long> s = {z, p};
  pair<pair<long long, long long>, pair<long long, long long>> pp = {f, s};
  if (dp.find(pp) != dp.end()) {
    return dp[pp];
  } else if (i == n and z > 0 and p == 0) {
    dp[pp] = recur(i - 1, k - 1, z - 1, 1);
    return dp[pp];
  } else if (p == 1 or z == 0 or i == 0) {
    dp[pp] = arr[i] + recur(i + 1, k - 1, z, 0);
    return dp[pp];
  }
  dp[pp] =
      arr[i] + max(recur(i + 1, k - 1, z, 0), recur(i - 1, k - 1, z - 1, 1));
  return dp[pp];
}
void solve() {
  dp.clear();
  long long k, z;
  cin >> n >> k >> z;
  for (long long i = 0; i < (n); i++) {
    cin >> arr[i];
  }
  long long ans = recur(1, k - 1, z, 0);
  ans += arr[0];
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long t;
  cin >> t;
  for (long long i = (1); i <= (t); i++) {
    solve();
  }
  return 0;
}

```