#include <iostream>
#include <vector>
#include <cmath>
#include <cassert>

using namespace std;

vector<unsigned long long> a(101,0);

// O(N) . Простой перебор. Для данного N перебираем
// все возможные разбиения числа на два слагаемых.
// Получаем две задачи меньшего размера. Решив их
// , собираем решение исходной выбрав то
// которое дает наибольшее произведение
unsigned long long task128_helper(unsigned int n) {
    if (a[n]) {
        return a[n];
    }
    for (unsigned int i = 1; i <= n/2; ++i) {
        a[n] = max(a[n], task128_helper(i)*task128_helper(n-i));
    }
    return a[n];
}

unsigned long long task128(unsigned int n){
    if (n) {
        return a[n] ? a[n] : task128_helper(n);
    }
    return 0;
}

// Посмотрев на то что получилось на выходе предыдущего алгоритма
// можно заметить что решения имеют вид 3^n*2^k. Это должно иметь под
// собой какое-то обоснование. Для начала поймем почему другие слагаемые не нужны.
// Например возмем 5. Если 5 разложить на сумму 3 и 2 , то видно что в таком случае
// произведение равно шести и вообще n <= 2^(n/2) и n <= 3^(n/3). Далее, функция
// 2*2*2...3*3 возрастает по мере увеличения числа троек. Из этого можно сделать
// вывод что нам выгоднее иметь как можно больше троек.
// Итак осталось только решить , что делать когда число не делится на 3
// Остаток 2 - Тут все просто просто берем эту двойку
// Остаток 1 - Уберем одну тройку и возьмем две двойки потому что 2*2>3*1
unsigned long long task128_fast(unsigned int n) {
    unsigned long long mult = 1;

    switch (n % 3) {
        case 1:
            mult = 4;
            n -= mult;
            break;
        case 2:
            mult = 2;
            n -= mult;
            break;
        default:
            mult = 1;
            break;
    }

    unsigned int k = n / 3;
    return mult * (unsigned long long)pow(3, k);
}

int main() {
    a[0] = 0;
    a[1] = 1;
    a[2] = 2;
    a[3] = 3;

    for(int i = 4; i < 101; ++i) {
        auto a = task128(i);
        auto b = task128_fast(i);
        cout << i << " -> " << a << " -> " << b << endl;
        assert(a == b);
    }

    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxjYXNzZXJ0PgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZlY3Rvcjx1bnNpZ25lZCBsb25nIGxvbmc+IGEoMTAxLDApOwoKLy8gTyhOKSAuINCf0YDQvtGB0YLQvtC5INC/0LXRgNC10LHQvtGALiDQlNC70Y8g0LTQsNC90L3QvtCz0L4gTiDQv9C10YDQtdCx0LjRgNCw0LXQvAovLyDQstGB0LUg0LLQvtC30LzQvtC20L3Ri9C1INGA0LDQt9Cx0LjQtdC90LjRjyDRh9C40YHQu9CwINC90LAg0LTQstCwINGB0LvQsNCz0LDQtdC80YvRhS4KLy8g0J/QvtC70YPRh9Cw0LXQvCDQtNCy0LUg0LfQsNC00LDRh9C4INC80LXQvdGM0YjQtdCz0L4g0YDQsNC30LzQtdGA0LAuINCg0LXRiNC40LIg0LjRhQovLyAsINGB0L7QsdC40YDQsNC10Lwg0YDQtdGI0LXQvdC40LUg0LjRgdGF0L7QtNC90L7QuSDQstGL0LHRgNCw0LIg0YLQvgovLyDQutC+0YLQvtGA0L7QtSDQtNCw0LXRgiDQvdCw0LjQsdC+0LvRjNGI0LXQtSDQv9GA0L7QuNC30LLQtdC00LXQvdC40LUKdW5zaWduZWQgbG9uZyBsb25nIHRhc2sxMjhfaGVscGVyKHVuc2lnbmVkIGludCBuKSB7CiAgICBpZiAoYVtuXSkgewogICAgICAgIHJldHVybiBhW25dOwogICAgfQogICAgZm9yICh1bnNpZ25lZCBpbnQgaSA9IDE7IGkgPD0gbi8yOyArK2kpIHsKICAgICAgICBhW25dID0gbWF4KGFbbl0sIHRhc2sxMjhfaGVscGVyKGkpKnRhc2sxMjhfaGVscGVyKG4taSkpOwogICAgfQogICAgcmV0dXJuIGFbbl07Cn0KCnVuc2lnbmVkIGxvbmcgbG9uZyB0YXNrMTI4KHVuc2lnbmVkIGludCBuKXsKICAgIGlmIChuKSB7CiAgICAgICAgcmV0dXJuIGFbbl0gPyBhW25dIDogdGFzazEyOF9oZWxwZXIobik7CiAgICB9CiAgICByZXR1cm4gMDsKfQoKLy8g0J/QvtGB0LzQvtGC0YDQtdCyINC90LAg0YLQviDRh9GC0L4g0L/QvtC70YPRh9C40LvQvtGB0Ywg0L3QsCDQstGL0YXQvtC00LUg0L/RgNC10LTRi9C00YPRidC10LPQviDQsNC70LPQvtGA0LjRgtC80LAKLy8g0LzQvtC20L3QviDQt9Cw0LzQtdGC0LjRgtGMINGH0YLQviDRgNC10YjQtdC90LjRjyDQuNC80LXRjtGCINCy0LjQtCAzXm4qMl5rLiDQrdGC0L4g0LTQvtC70LbQvdC+INC40LzQtdGC0Ywg0L/QvtC0Ci8vINGB0L7QsdC+0Lkg0LrQsNC60L7QtS3RgtC+INC+0LHQvtGB0L3QvtCy0LDQvdC40LUuINCU0LvRjyDQvdCw0YfQsNC70LAg0L/QvtC50LzQtdC8INC/0L7Rh9C10LzRgyDQtNGA0YPQs9C40LUg0YHQu9Cw0LPQsNC10LzRi9C1INC90LUg0L3Rg9C20L3Riy4KLy8g0J3QsNC/0YDQuNC80LXRgCDQstC+0LfQvNC10LwgNS4g0JXRgdC70LggNSDRgNCw0LfQu9C+0LbQuNGC0Ywg0L3QsCDRgdGD0LzQvNGDIDMg0LggMiAsINGC0L4g0LLQuNC00L3QviDRh9GC0L4g0LIg0YLQsNC60L7QvCDRgdC70YPRh9Cw0LUKLy8g0L/RgNC+0LjQt9Cy0LXQtNC10L3QuNC1INGA0LDQstC90L4g0YjQtdGB0YLQuCDQuCDQstC+0L7QsdGJ0LUgbiA8PSAyXihuLzIpINC4IG4gPD0gM14obi8zKS4g0JTQsNC70LXQtSwg0YTRg9C90LrRhtC40Y8KLy8gMioyKjIuLi4zKjMg0LLQvtC30YDQsNGB0YLQsNC10YIg0L/QviDQvNC10YDQtSDRg9Cy0LXQu9C40YfQtdC90LjRjyDRh9C40YHQu9CwINGC0YDQvtC10LouINCY0Lcg0Y3RgtC+0LPQviDQvNC+0LbQvdC+INGB0LTQtdC70LDRgtGMCi8vINCy0YvQstC+0LQg0YfRgtC+INC90LDQvCDQstGL0LPQvtC00L3QtdC1INC40LzQtdGC0Ywg0LrQsNC6INC80L7QttC90L4g0LHQvtC70YzRiNC1INGC0YDQvtC10LouCi8vINCY0YLQsNC6INC+0YHRgtCw0LvQvtGB0Ywg0YLQvtC70YzQutC+INGA0LXRiNC40YLRjCAsINGH0YLQviDQtNC10LvQsNGC0Ywg0LrQvtCz0LTQsCDRh9C40YHQu9C+INC90LUg0LTQtdC70LjRgtGB0Y8g0L3QsCAzCi8vINCe0YHRgtCw0YLQvtC6IDIgLSDQotGD0YIg0LLRgdC1INC/0YDQvtGB0YLQviDQv9GA0L7RgdGC0L4g0LHQtdGA0LXQvCDRjdGC0YMg0LTQstC+0LnQutGDCi8vINCe0YHRgtCw0YLQvtC6IDEgLSDQo9Cx0LXRgNC10Lwg0L7QtNC90YMg0YLRgNC+0LnQutGDINC4INCy0L7Qt9GM0LzQtdC8INC00LLQtSDQtNCy0L7QudC60Lgg0L/QvtGC0L7QvNGDINGH0YLQviAyKjI+MyoxCnVuc2lnbmVkIGxvbmcgbG9uZyB0YXNrMTI4X2Zhc3QodW5zaWduZWQgaW50IG4pIHsKICAgIHVuc2lnbmVkIGxvbmcgbG9uZyBtdWx0ID0gMTsKCiAgICBzd2l0Y2ggKG4gJSAzKSB7CiAgICAgICAgY2FzZSAxOgogICAgICAgICAgICBtdWx0ID0gNDsKICAgICAgICAgICAgbiAtPSBtdWx0OwogICAgICAgICAgICBicmVhazsKICAgICAgICBjYXNlIDI6CiAgICAgICAgICAgIG11bHQgPSAyOwogICAgICAgICAgICBuIC09IG11bHQ7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIGRlZmF1bHQ6CiAgICAgICAgICAgIG11bHQgPSAxOwogICAgICAgICAgICBicmVhazsKICAgIH0KCiAgICB1bnNpZ25lZCBpbnQgayA9IG4gLyAzOwogICAgcmV0dXJuIG11bHQgKiAodW5zaWduZWQgbG9uZyBsb25nKXBvdygzLCBrKTsKfQoKaW50IG1haW4oKSB7CiAgICBhWzBdID0gMDsKICAgIGFbMV0gPSAxOwogICAgYVsyXSA9IDI7CiAgICBhWzNdID0gMzsKCiAgICBmb3IoaW50IGkgPSA0OyBpIDwgMTAxOyArK2kpIHsKICAgICAgICBhdXRvIGEgPSB0YXNrMTI4KGkpOwogICAgICAgIGF1dG8gYiA9IHRhc2sxMjhfZmFzdChpKTsKICAgICAgICBjb3V0IDw8IGkgPDwgIiAtPiAiIDw8IGEgPDwgIiAtPiAiIDw8IGIgPDwgZW5kbDsKICAgICAgICBhc3NlcnQoYSA9PSBiKTsKICAgIH0KCiAgICByZXR1cm4gMDsKfQ==