Померти молодим

Діаграма Юнга — це відомий спосіб опису розбиття додатного цілого числа. Розбиття числа $n$ — це представлення у вигляді суми одного або кількох цілих чисел n = m_1 + m_2 + \ldots + m_k, де m_1 \geq m_2 \geq \ldots \geq m_k.

Діаграма складається з $n$ клітинок, розташованих у $k$ рядках, де $k$ — це кількість доданків у розбитті. Рядок, що представляє число m_i, містить m_i клітинок. Усі рядки вирівняні по лівому краю та відсортовані від найдовшого до найкоротшого.

Діаграма на зображенні нижче відповідає розбиттю 10 = 5 + 3 + 2.

Іноді можливо вписати одну діаграму Юнга в іншу. Діаграма $X$ може бути вписана в діаграму $Y$, якщо можливо видалити деякі клітинки з діаграми $Y$ так, щоб вона перетворилася на діаграму $X$. Зверніть увагу, що дозволено лише видаляти деякі клітинки, не дозволено обертати або перевертати діаграму. Наприклад, на зображенні нижче показано, що діаграма для 5 = 3 + 2 може бути вписана в діаграму для 10 = 5 + 3 + 2.

З іншого боку, наприклад, неможливо вписати діаграму для 8 = 4 + 4 в діаграму для 10 = 5 + 3 + 2.

Дано $n$, ваше завдання — знайти таке розбиття $n$, щоб відповідна діаграма Юнга мала найбільшу можливу кількість діаграм, які можуть бути вписані в неї.

Наприклад, існує $36$ діаграм Юнга, які можуть бути вписані в діаграму для 10 = 5 + 3 + 2. Однак це не максимальне можливе значення. Діаграма для 10 = 4 + 2 + 2 + 1 + 1 має краще значення, існує $41$ діаграма, яка може бути вписана в неї.