Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. The Elder Trolls IV: Oblivon

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya plays The Elder Trolls IV: Oblivon. Oh, those creators of computer games! What they do not come up with! Absolutely unique monsters have been added to the The Elder Trolls IV: Oblivon. One of these monsters is Unkillable Slug. Why it is "Unkillable"? Firstly, because it can be killed with cutting weapon only, so lovers of two-handed amber hammers should find suitable knife themselves. Secondly, it is necessary to make so many cutting strokes to Unkillable Slug. Extremely many. Too many!

Vasya has already promoted his character to 80-th level and in order to gain level 81 he was asked to kill Unkillable Slug. The monster has a very interesting shape. It looks like a rectangular parallelepiped with size *x* × *y* × *z*, consisting of undestructable cells 1 × 1 × 1. At one stroke Vasya can cut the Slug along an imaginary grid, i.e. cut with a plane parallel to one of the parallelepiped side. Monster dies when amount of parts it is divided reaches some critical value.

All parts of monster do not fall after each cut, they remains exactly on its places. I. e. Vasya can cut several parts with one cut.

Vasya wants to know what the maximum number of pieces he can cut the Unkillable Slug into striking him at most *k* times.

Vasya's character uses absolutely thin sword with infinite length.

Input

The first line of input contains four integer numbers *x*, *y*, *z*, *k* (1 ≤ *x*, *y*, *z* ≤ 10^{6}, 0 ≤ *k* ≤ 10^{9}).

Output

Output the only number — the answer for the problem.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Examples

Input

2 2 2 3

Output

8

Input

2 2 2 1

Output

2

Note

In the first sample Vasya make 3 pairwise perpendicular cuts. He cuts monster on two parts with the first cut, then he divides each part on two with the second cut, and finally he divides each of the 4 parts on two.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/19/2017 08:33:36 (p1).

Desktop version, switch to mobile version.

User lists

Name |
---|