codeforces534B

Covered Path

The on-board computer on Polycarp's car measured that the car speed at the beginning of some section of the path equals v₁ meters per second, and in the end it is v₂meters per second. We know that this section of the route took exactly t seconds to pass.

Assuming that at each of the seconds the speed is constant, and between seconds the speed can change at most by d meters per second in absolute value (i.e., the difference in the speed of any two adjacent seconds does not exceed d in absolute value), find the maximum possible length of the path section in meters.

Input

The first line contains two integers v₁ and v₂ (1 ≤ v₁, v₂ ≤ 100) — the speeds in meters per second at the beginning of the segment and at the end of the segment, respectively.

The second line contains two integers t (2 ≤ t ≤ 100) — the time when the car moves along the segment in seconds, d (0 ≤ d ≤ 10) — the maximum value of the speed change between adjacent seconds.

It is guaranteed that there is a way to complete the segment so that:

the speed in the first second equals v₁,
the speed in the last second equals v₂,
the absolute value of difference of speeds between any two adjacent seconds doesn't exceed d.

Output

Print the maximum possible length of the path segment in meters.

Examples

Input

5 6
4 2

Output

Input

10 10
10 0

Output

Note

In the first sample the sequence of speeds of Polycarpus' car can look as follows: 5, 7, 8, 6. Thus, the total path is 5 + 7 + 8 + 6 = 26 meters.

In the second sample, as d = 0, the car covers the whole segment at constant speed v = 10. In t = 10 seconds it covers the distance of 100 meters.

sol：一开始以为是小学奥数一样的东西，写了一堆特判后发现根本讨论不完，于是彻底自闭

发现是个很裸的dp，dp[i][j]表示第 i 秒，速度为 j 的最大路程

Ps：初速度100，加速度10，加速时间100，要开1105的数组，唯一的坑点

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');    return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=2005;
int v1,v2,t,d,dp[105][N];
int main()
{
    int i,j,k;
    R(v1); R(v2); R(t); R(d);
    memset(dp,-1,sizeof dp);
    dp[1][v1]=v1;
    for(i=1;i<t;i++)
    {
        for(j=0;j<=i*d+v1;j++) if(dp[i][j]!=-1)
        {
            for(k=-d;k<=d;k++)
            {
                if(j+k>=0) dp[i+1][j+k]=max(dp[i+1][j+k],dp[i][j]+j+k);
            }
        }
    }
//    for(i=1;i<=t;i++)
//    {
//        for(j=0;j<=v2;j++) printf("%d ",dp[i][j]); puts("");
//    }
    Wl(dp[t][v2]);
    return 0;
}
/*
Input
5 6
4 2
Output
26

Input
10 10
10 0
Output
100

Input
87 87
2 10
Output
174

Input
1 11
6 2
Output
36

Input
100 1
100 10
Output
29305

input
100 1
100 1
output
5050
*/

View Code