#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; ll T; vl l_dif; vl r_dif; vl ls1; vl ls2; ll dp[1001][1001]; bool check(ll speed) { speed *= T; ls1 = {}; ls2 = {}; forall(it,l_dif) ls1.pb(-it/2); forall(it,r_dif) ls2.pb(-it/2); rep(i,siz(ls1)+1) rep(j,siz(ls2)+1) dp[i][j] = -1; dp[0][0] = speed; rep(i,siz(ls1)+1) rep(j,siz(ls2)+1) { if(dp[i][j] <= -1) continue; if(i != siz(ls1) && dp[i][j] + ls1[i] >= 0) dp[i+1][j] = max(dp[i+1][j],dp[i][j]+ls1[i]+speed); if(j != siz(ls2) && dp[i][j] + ls2[j] >= 0) dp[i][j+1] = max(dp[i][j+1],dp[i][j]+ls2[j]+speed); } return dp[siz(ls1)][siz(ls2)] >= 0; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); int n,k; cin >> n >> k >> T; vl arr(n); rep(i,n) cin >> arr[i]; rep(i,n) arr[i] *= 2; T *= 2; rep(i,k-1) l_dif.pb(arr[i+1]-arr[i]); reverse(all(l_dif)); rep2(i,k-1,n-2) r_dif.pb(arr[i+1]-arr[i]); ll l = 0; ll r = 3e9; ll ans = -1; while(l <= r) { ll mid = (l+r)/2; if(check(mid)) { ans = mid; r = mid-1; } else { l = mid+1; } } cout << ans << "\n"; }