Будівництво храму#6983
Гноми Середзем'я відомі своєю майстерністю у шахтарській та ковальській справі, але вони також є майстрами будівничими. У часи драконів гноми з'ясували, що найстійкішими до нападів наземними спорудами були усічені квадратні піраміди (квадратна піраміда, яка не доходить до вершини, а має плоский квадрат зверху).
Гноми знали, якою має бути ідеальна форма споруди, зважаючи на бажану висоту та розміри квадратної основи внизу і вгорі. Зазвичай у них було три різні розміри кубічних цеглин для роботи. Їхньою метою було максимізувати об'єм такої споруди, дотримуючись наступних правил:
Споруда складається з рівнів; кожен рівень є квадратом із цеглин одного розміру. Жодна частина цеглини не може виходити за межі ідеальної форми — ані з боків, ані зверху. Отримана конструкція матиме зубчасті сторони і може бути нижчою за ідеальну, але має повністю розміщуватися в межах ідеального проєкту. Зображення праворуч — це вертикальний розріз однієї з таких веж.
Немає обмежень на кількість цеглин кожного типу, які можна використати.
У кожному рядку містяться ідеальна висота храму, розміри квадратної основи знизу та зверху (усі три — невід'ємні цілі числа, не більші за ), а далі — три розміри кубічних цеглин (усі три — невід'ємні цілі числа, не більші за ). Введення завершується при досягненні кінця файлу.
Для кожного рядка вхідних даних потрібно вивести максимальний можливий об'єм на основі поданих правил, по одному значенню на рядок.
Приклад 1