Problem

There are $ N $ arithmetic progressions with the number of terms $ L $. The first term of the $ i $ arithmetic progression is $ a_i $ and the tolerance is $ d_i $. Arrange the first sequence, the second sequence, ..., the $ N $ sequence in order from the first sequence, and let the resulting sequence be $ A $. Then, when you select an arbitrary interval of length $ K $ from $ A $ and create a new sequence $ B $, maximize the sum of the sequence $ B $.

Constraints

The input satisfies the following conditions.

* $ 1 \ leq N \ leq 10 ^ 5 $
* $ 1 \ leq L \ leq 10 ^ 5 $
* $ 1 \ leq K \ leq N \ times L $
* $ 0 \ leq a_i \ leq 10 ^ 5 $
* $ 1 \ leq d_i \ leq 10 ^ 3 $
* All inputs are integers

Input

The input is given in the following format.

$ N $ $ L $ $ K $
$ a_1 $ $ d_1 $
$ a_2 $ $ d_2 $
...
$ a_N $ $ d_N $


Three integers $ N $, $ L $, $ K $ are given on the first line, separated by blanks.
In the following $ N $ row, the $ i $ arithmetic progression information $ a_i $, $ d_i $ is given, separated by blanks.

Output

Outputs the maximum value of the sum of the sequence $ B $ on one line.

Examples

Input

3 3 5
0 3
2 2
4 1


Output

25


Input

3 3 5
0 10
8 1
11 1


Output

58
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 100005
typedef long long ll;

ll calc(ll a,ll d,ll n){
  if(n==0)return 0;
  return ( a+a+d*(n-1) )*n/2;
}

ll N,X,L;
ll a[MAX_N],d[MAX_N];

ll solve2();

ll solve(){

  ll res=0, val=0;

  
  int j=0;
  for(int i=0;i<N;i++){
    while( j < i+L/X ){
      val+=(a[j]+a[j]+(X-1)*d[j])*X/2;
      j++;
      if(j>=N)break;
    }
    
    res=max(res,val);
    if(j>=N)break;
    
    ll aj =a[j]+(L%X)*d[j];
    double A = -0.5*d[i] + 0.5*d[j];
    double B = -(a[i]-0.5*d[i]) + (aj-0.5*d[j]);
    
    double left=0, right =X-L%X , ll , rr, lv,rv;
    
    for(int p=0;p<100;p++){
      ll=(left+left+right)/3.0;
      rr=(right+right+left)/3.0;
      lv=A*ll*ll+B*ll;
      rv=A*rr*rr+B*rr;
      if(lv < rv)left=ll;
      else right=rr;
    }


    res=max(res, val + calc(a[j],d[j],L%X) );
    res=max(res, val + calc(a[j],d[j],X) - calc(a[i],d[i],X-L%X) );
    
    long long mm = left;
    /*
    cout<<"i="<<i<<" j="<<j<<endl;
    cout<<"val="<<val<<endl;
    cout<<"mm="<<mm<<endl;
    cout<<val + calc(a[j],d[j],L%X)<<endl;
    cout<<endl;
    */
    
    for( long long  dm = mm-1; dm<=mm+1; dm++ ){
      if(dm<0 || dm>(X-L%X) )continue;
      res=max(res, val + calc(a[j],d[j],L%X+dm) - calc(a[i],d[i],dm) );
    }
  
    if(i>0 && L%X>0){
      
      long long fa = a[i-1]+(X-1)*d[i-1];
      long long fd = d[i-1]*-1;
      long long sa = a[j]+(L%X-1)*d[j];
      long long sd = d[j]*-1;

      A = ( fd*fd*0.5 ) - ( sd*sd*0.5 );
      B = ( fa-fd*0.5 ) - ( sa-sd*0.5 );
      
      left=0,right=L%X;
      for(int p=0;p<100;p++){
        ll=(left+left+right)/3.0;
        rr=(right+right+left)/3.0;
        lv=A*ll*ll+B*ll;
        rv=A*rr*rr+B*rr;
        if(lv < rv)left=ll;
        else right=rr;
      }

      mm = left;
      for( long long  dm = mm-1; dm<=mm+1; dm++ ){
        if(dm<0 || dm>(L%X) )continue;
        res=max(res, val + calc(a[j],d[j],L%X) + calc(fa,fd,dm) - calc(sa,sd,dm) );
      }
      
      
    }
    val-=(a[i]+a[i]+(X-1)*d[i])*X/2;
  }
  return res;
}

int main(){
  scanf("%lld %lld %lld",&N,&X,&L);
  for(int i=0;i<N;i++){
    scanf("%lld %lld",&a[i],&d[i]);
  }
  ll ans=solve();

  for(int i=0;i<N;i++){
    a[i]= a[i]+d[i]*(X-1);
    d[i]*=-1;
  }
  printf("%lld\n",ans);
  return 0;
}

ll solve2(){
  ll res=0;
  for(int i=0;i<N;i++){
    ll A = a[i] + (X-1)*d[i];
    ll B = a[i] + (X-L)*d[i];
    ll sum = (A+B)*L/2;
    res=max(res,sum);
  }
  return res;
}