ЗАДАЧА D
Платья
| Имя входного файла: | dress.in |
| Имя выходного файла: | dress.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 Мб |
Хватит, хватит, надоело! Моя жизнь совершенно беспросветная, я живу как крестьянка крепостная. У меня четыре платья есть вечерних, шелковых, а одеть их некуда. Нет, все решено - мы завтра же уезжаем на курорт.
Из мультфильма «Каникулы в Простоквашино»
И мама Римма, твердо намеренная поехать завтра же на курорт, отправилась собирать чемоданы. А как известно, сборы на курорт – это очень важная и сложная задача, которую не решить без применения информационных технологий. Ведь взять хочется как можно больше разных вещей, а чемоданы не резиновые. Поэтому мама сразу же поручила дяде Федору разработать программу для вычисления оптимального состава багажа.
В гардеробе мамы есть A платьев, B шляпок и C сумочек, но в чемодан помещается не более N вещей. Мама хочет так выбрать одежду для отдыха, чтобы можно было совершить как можно больше светских выходов. На каждый светский выход мама будет надевать наряд, состоящий из платья, шляпки и сумочки, причем по правилам этикета, наряды, одетые на любые два светских раута, должны отличаться хотя бы двумя вещами. Помогите дяде Федору определить, какое максимальное количество светских выходов сможет совершить его мама в отпуске при оптимальной упаковке чемодана.
Входные данные
Единственная строка входного файла содержит четыре целых числа A, B, C и N (0 <= A, B, C, N <= 10000).
Выходные данные
В выходной файл выведите единственное целое число – максимально возможное количество нарядов, различающихся хотя бы двумя вещами, которые можно составить при оптимальном выборе багажа.
Пример
| dress.in | dress.out |
|---|---|
|
|
|
|