//g++ 2.cpp -std=c++14 -O2 -I . #include using namespace std; #include using namespace atcoder; using ll = long long; using ld = long double; using vi = vector; using vvi = vector; using vll = vector; using vvll = vector; using vld = vector; using vvld = vector; using vst = vector; using vvst = vector; #define fi first #define se second #define pb push_back #define eb emplace_back #define pq_big(T) priority_queue,less> #define pq_small(T) priority_queue,greater> #define all(a) a.begin(),a.end() #define rep(i,start,end) for(ll i=start;i<(ll)(end);i++) #define per(i,start,end) for(ll i=start;i>=(ll)(end);i--) #define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end()) vvi dp(10050,vi(5050,0)); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,v,c; cin>>n>>v>>c; vector> gd(n); rep(i,0,n){ int x,y; cin>>x>>y; gd[i]={x,y}; } int ans=0; rep(i,0,n){ auto [x,y]=gd[i]; rep(j,0,v+1){ dp[i+1][j]=dp[i][j]; ans=max(ans,dp[i+1][j]); } per(j,v,0){ if(j>=x){ dp[i+1][j]=max(dp[i+1][j],dp[i][j-x]+y+c); ans=max(ans,dp[i+1][j]); } } } rep(i,0,n){ auto [x,y]=gd[i]; rep(j,0,v+1){ dp[n+i+1][j]=dp[n+i][j]; ans=max(ans,dp[n+i+1][j]); } rep(j,0,v+1){ if(j+x<=v){ dp[n+i+1][j+x]=max(dp[n+i+1][j+x],dp[n+i+1][j]+y); ans=max(ans,dp[n+i+1][j+x]); } } } cout<