Malvina's Vacation#2698
Malvina, a renowned beauty, has dresses, hats, and handbags in her wardrobe. However, her suitcase can hold no more than items. Malvina wants to select clothes for her vacation in such a way that she can make as many social appearances as possible. For each appearance, Malvina will wear an outfit consisting of a dress, a hat, and a handbag. According to etiquette, the outfits worn to any two social events must differ by at least two items. Help Malvina determine the maximum number of social appearances she can make by optimally packing her suitcase.
The input contains a single line with four integers: , , , and (0 < a, , , n < 10000).
Print a single integer — the maximum number of outfits, each differing by at least two items, that can be assembled by the optimal selection of items for the suitcase.
Example 1