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 个成对的垂直切割。他用第一刀将怪物切成两部分,然后用第二刀将每个部分分成两部分,最后他将四个部分中的每部分分成两部分。