CARINA - Carina

Little Petar had played the Flappy Bird game for far too long, and got bored of the fact that the bird never gets tired and always jumps with the same intensity. As this felt very unnatural, he had decided to make his own version of the game, dubbed PetarVBird™. However, he was immediately reported to the police for violating intellectual property laws, and as such his options for distributing the game abroad are very limited.

Petar made a specific number of copies of the game, and intends to transport them from the company (location A) to the distributer (location B). To do this, he has in his possession a single truck, capable of carrying a limited amount of copies at once. Along the way from A to B there is a series of customs checkpoints; if Petar is carrying at least one copy of the game in his truck at the moment of arrival to the checkpoint, he is obliged to give a copy to the customs officers as a bribe. It is possible to unload the copies at the checkpoint, and then load them back in again. In addition, to avoid making the traffic police suspicious, Petar does not want to return back to location A more than X times.

Petar is interested in the maximal amount of copies of the game he can successfully deliver to location B, under these constraints.

Input

The first and only line of the standard input contains four integers: N, C, L and X, representing the number of copies, the truck's capacity, the number of checkpoints between A and B and the maximal amount of returns to A allowed, respectively.

Output

Write to the first and only line of the standard output a single integer, representing the maximal amount of copies of the game that can be delivered to location B.

Example

Input:
4000 1000 1000 1

Output:
500

Explanation

Petar may first load up his truck with 1000 copies, drive them to the 500th checkpoint along the way, and unload the 500 copies he has left. After that he returns to A and does the same thing again. Now there are 1000 copies at the 500th checkpoint, which Petar will all collect and carry on to B, with 500 copies delivered. There is no strategy that will result in more copies successfully delivered to B.

Constraints

  • 1 <= N, C, L <= 1018
  • 0 <= X <= 106

Added by:PetarV
Date:2015-04-08
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Serbian Qualifications 2014 (Own problem)

hide comments
2015-08-14 15:25:55 :D
I think you can interpret is like this: every time you get to a checkpoint, if you carry something pay one unit. Then unload or load copies on checkpoint and move to next or previous point.
2015-04-09 16:39:49 Phong
Does Petar has to pay one copy for each arrival at one checkpoint or he just have to pay one for each checkpoint he pass ?

Re (PetarV): every time he reaches a checkpoint, if he's carrying something, he must pay; regardless of whether he visited that checkpoint before or not. (I believe the sample test explanation clarifies that).

Last edit: 2015-04-09 22:11:40
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.