English · Original
Chinese · Translation
Formal · Original
Vasya 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_ ≤ 106, 0 ≤ _k_ ≤ 109).
## 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_).
[samples]
## 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.
Vasya 正在玩《上古卷轴 IV：遗忘》。那些游戏开发者啊！他们想得出什么点子！《上古卷轴 IV：遗忘》中加入了完全独特的怪物，其中一个就是“不可杀死的蛞蝓”。为什么叫“不可杀死”？首先，因为它只能用切割武器击杀，所以喜欢双手琥珀重锤的玩家必须自己找一把合适的刀。其次，必须对“不可杀死的蛞蝓”进行如此多的切割动作——极其多，多到无法想象！
Vasya 已经将他的角色提升到第 80 级，为了升到第 81 级，他被要求击杀“不可杀死的蛞蝓”。这个怪物的形状非常有趣，它看起来像一个尺寸为 $x × y × z$ 的长方体，由无数个不可摧毁的 $1 × 1 × 1$ 单元格组成。每次攻击，Vasya 可以沿着虚拟网格切割，即用一个平行于长方体某一侧面的平面进行切割。当怪物被分割成的块数达到某个临界值时，它就会死亡。
每次切割后，怪物的所有部分都不会掉落，仍保持在原位。也就是说，一次切割可以同时切开多个部分。
Vasya 想知道，在最多攻击 $k$ 次的情况下，他最多能将“不可杀死的蛞蝓”切成多少块？
Vasya 的角色使用一把绝对细薄、长度无限的剑。
输入的第一行包含四个整数 $x, y, z, k$（$1 ≤ x, y, z ≤ 10^6, 0 ≤ k ≤ 10^9$）。
输出仅一个数字——本题的答案。
请勿在 C++ 中使用 _%lld_ 标识符读写 64 位整数。推荐使用 _cout_（也可以使用 _%I64d_）。
在第一个样例中，Vasya 进行了三次两两垂直的切割。第一次切割将怪物分成两部分，第二次切割将每部分再分成两部分，最后第三次切割将四个部分中的每一个再分成两部分。
## Input
输入的第一行包含四个整数 $x, y, z, k$（$1 ≤ x, y, z ≤ 10^6, 0 ≤ k ≤ 10^9$）。
## Output
输出仅一个数字——本题的答案。请勿在 C++ 中使用 _%lld_ 标识符读写 64 位整数。推荐使用 _cout_（也可以使用 _%I64d_）。
[samples]
## Note
在第一个样例中，Vasya 进行了三次两两垂直的切割。第一次切割将怪物分成两部分，第二次切割将每部分再分成两部分，最后第三次切割将四个部分中的每一个再分成两部分。
**Definitions**
Let $ x, y, z \in \mathbb{Z}^+ $ denote the dimensions of the rectangular parallelepiped.
Let $ k \in \mathbb{Z}_{\geq 0} $ denote the maximum number of allowed planar cuts.
**Constraints**
1. $ 1 \leq x, y, z \leq 10^6 $
2. $ 0 \leq k \leq 10^9 $
**Objective**
Maximize the number of pieces $ P $ the parallelepiped can be divided into using at most $ k $ planar cuts, where each cut is parallel to one of the three coordinate planes (i.e., axis-aligned).
The maximum number of pieces obtainable with $ a $ cuts parallel to the $ yz $-plane, $ b $ cuts parallel to the $ xz $-plane, and $ c $ cuts parallel to the $ xy $-plane, where $ a + b + c \leq k $, is:
$$
P = (a + 1)(b + 1)(c + 1)
$$
The objective is to choose non-negative integers $ a, b, c $ such that:
$$
a + b + c \leq k
$$
and $ P = (a + 1)(b + 1)(c + 1) $ is maximized, **subject to** the physical constraints:
$$
a \leq x - 1, \quad b \leq y - 1, \quad c \leq z - 1
$$
**Final Objective**
Compute:
$$
\max_{\substack{a,b,c \in \mathbb{Z}_{\geq 0} \\ a + b + c \leq k \\ a \leq x-1 \\ b \leq y-1 \\ c \leq z-1}} (a+1)(b+1)(c+1)
$$
API Response (JSON)
{
"problem": {
"name": "A. The Elder Trolls IV: Oblivon",
"description": {
"content": "Vasya 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 th",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF73A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Vasya 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 th...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Vasya 正在玩《上古卷轴 IV：遗忘》。那些游戏开发者啊！他们想得出什么点子！《上古卷轴 IV：遗忘》中加入了完全独特的怪物，其中一个就是“不可杀死的蛞蝓”。为什么叫“不可杀死”？首先，因为它只能用切割武器击杀，所以喜欢双手琥珀重锤的玩家必须自己找一把合适的刀。其次，必须对“不可杀死的蛞蝓”进行如此多的切割动作——极其多，多到无法想象！\n\nVasya 已经将他的角色提升到第 80 级，为了升到...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ x, y, z \\in \\mathbb{Z}^+ $ denote the dimensions of the rectangular parallelepiped. \nLet $ k \\in \\mathbb{Z}_{\\geq 0} $ denote the maximum number of allowed planar cuts.\n\n**Con...",
"is_translate": false,
"language": "Formal"
}
]
}