73A.md (2195B)
1 Source: https://codeforces.com/problemset/problem/73/A 2 3 A. The Elder Trolls IV: Oblivon 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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! 22 23 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. 24 25 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. 26 27 Vasya wants to know what the maximum number of pieces he can cut the Unkillable Slug into striking him at most *k* times. 28 29 Vasya's character uses absolutely thin sword with infinite length. 30 31 Input 32 33 The first line of input contains four integer numbers *x*, *y*, *z*, *k* (1 ≤ *x*, *y*, *z* ≤ 106, 0 ≤ *k* ≤ 109). 34 35 Output 36 37 Output the only number — the answer for the problem. 38 39 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). 40 41 Examples 42 43 Input 44 45 ``` 46 2 2 2 3 47 ``` 48 49 Output 50 51 ``` 52 8 53 ``` 54 55 Input 56 57 ``` 58 2 2 2 1 59 ``` 60 61 Output 62 63 ``` 64 2 65 ``` 66 67 Note 68 69 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.