Problem J
Cheating Luck

Donald is playing a game of cards against his cousin Gladstone. Each round proceeds as follows:

1. Donald chooses an (integer) amount of coins and both of the cousins puts that many coins in the pot.

2. The cards are dealt.

3. The game is played.

4. The player who won gets all the coins in the pot.

This continues until either $n$ rounds have been played, or until one of the players have run out of coins.

Unfortunately, Gladstone is quite possibly the luckiest person alive. As his luck would let him win every single round, the cousins’ game would surely lead to a quick economic demise for Donald. To balance the situation, Donald has hired his nephews to distract Gladstone a few times, by giving him a prank phone call between steps 2 and 3 above. Every round in which Gladstone is distracted, Donald is able to look at Gladstone’s cards and can with this extra knowledge and some card swapping be certain to win the round.

But things are still not easy for Donald. Gladstone will not be distracted during every round, and Donald has no way of knowing in advance during which rounds Gladstone will be distracted, which effectively means that Gladstone’s luck will take its course and do its best to cheat Donald out of his hard-earned coins. Is it still possible for Donald to come out richer from this experience, by being careful in how he chooses his bets?

Note that in step 2, Donald can never bet more coins than he has, or more coins than Gladstone has.

Input

The input consists of four integers $d$, $g$, $n$, and $k$, where $1 \le d, g \le 1000$ are the amounts of coins Donald and Gladstone initially have, $1 \le n \le 50$ is the number of rounds they will play, and $0 \le k \le n$ is the number of rounds during which Gladstone will be distracted.

Output

Write a single line containing an integer $M$ giving the maximum amount of coins Donald can be certain to have at the end of the game.

2 10 3 2

4

10 10 5 0

10

1 1000 10 9

1