← 返回题目列表

Codeforces · 73/A

A. 上古巨魔 IV:湮没

中文机器翻译题面 查看原题

Vasya 扮演《上古巨魔 IV:湮没》。哦,那些电脑游戏的创造者!他们想不出什么! 《上古巨魔 IV:湮没》中添加了绝对独特的怪物。这些怪物之一是无法杀死的鼻涕虫。为什么说是“杀不死”呢?首先,因为它只能用切割武器杀死,所以双手琥珀锤的爱好者应该自己找到合适的刀。其次,有必要对不死之蛞蝓进行如此多次的切割。极其多。太多了!

Vasya 已经将他的角色提升到了 80 级,为了获得 81 级,他被要求杀死不可杀死的鼻涕虫。怪物的形状非常有趣。它看起来像一个大小为 x × y × z 的长方体,由不可破坏的 1 × 1 × 1 单元组成。 Vasya 可以一口气沿着假想的网格切割蛞蝓,即用平行于平行六面体一侧的平面进行切割。当怪物被分割的数量达到某个临界值时,怪物就会死亡。

每次切割后,怪物的所有部分都不会掉落,它们仍然准确地保留在原位。 IE。 Vasya 可以一次切割多个零件。

Vasya 想知道他最多可以将不灭蛞蝓切成多少块来击中他最多 k 次。

Vasya的角色使用无限长度的绝对细剑。

输入

输入的第一行包含四个整数 x, y, z, k (1 ≤ x, y, z ≤ 106, 0 ≤ k ≤ 109)。

输出

输出唯一的数字——问题的答案。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cout (也可以使用 %I64d)。

示例

输入 #1

2 2 2 3

输出 #1

8

输入 #2

2 2 2 1

输出 #2

2

注意

在第一个样本中,Vasya 进行 3 个成对的垂直切割。他用第一刀将怪物切成两部分,然后用第二刀将每个部分分成两部分,最后他将四个部分中的每部分分成两部分。