<p>Given an integer <code>n</code>, break it into the sum of <code>k</code> <strong>positive integers</strong>, where <code>k &gt;= 2</code>, and maximize the product of those integers.</p>

<p>Return <em>the maximum product you can get</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong> 2 = 1 + 1, 1 &times; 1 = 1.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 10
<strong>Output:</strong> 36
<strong>Explanation:</strong> 10 = 3 + 3 + 4, 3 &times; 3 &times; 4 = 36.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 58</code></li>
</ul>

class Solution {
public:
//--------------------------------->ओम नमो भगवते  वासुदेवाय<---------------------------------------------------------------
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡋⠉⢋⣝⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⣆⣘⣿⢿⡟⡷⢶⣤⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢉⣡⡾⠃⣷⠀⡈⠙⢿⣶⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣴⡿⠋⢠⣾⠏⣸⣿⣦⡀⠙⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⡟⠋⠀⠀⣿⡏⠀⣿⠁⠹⣿⡄⠘⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠋⠀⠀⠀⠸⣿⡇⠀⣿⠀⠀⢹⣿⠀⢻⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⡟⠀⠀⣀⣤⣶⣿⡿⢄⠘⢇⠀⢸⣿⡇⣼⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀	⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⡇⠀⣼⡿⠋⠁⠀⠀⠀⢀⣀⣀⣸⣿⢠⡿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⣀⣠⣤⣤⣶⣶⣶⣶⣦⣤⣈⠗⢰⡟⠀⠀⣠⣴⠾⠟⠛⠛⠛⠻⣷⡛⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠘⠿⢿⣿⣍⠀⠀⠀⠀⠀⠉⠛⢿⣬⠇⢠⡾⠋⠀⠀⠀⠀⠀⠀⠲⣦⠙⢷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠘⢿⣷⠀⠀⠀⠀⠀⠀⠀⢻⣧⠋⠀⠀⠀⠀⡀⠀⠀⠀⠀⠘⣧⠀⠙⣷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠈⢿⣧⠀⠀⢠⡀⠀⠀⢨⡿⠀⠀⠀⠀⠀⠉⠒⠒⠶⣦⡀⠙⢷⣶⣾⢿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⢸⣿⠀⠀⠀⠳⠤⠴⠟⠁⠀⢀⠀⠀⠀⠀⠀⠻⠟⠚⠃⠀⠀⠀⠸⠮⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠈⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⣧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠹⣷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⢶⣤⣤⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣧⠀⠀⠀⠀⣼⣧⡀⠀⠀⠀⠀
// ⠀⣀⣀⣀⣀⠀⠀⠘⢻⣦⣀⠀⠀⢠⣄⠀⢠⣴⣦⣄⠀⠉⠙⠻⢿⣦⡀⠀⠀⠀⠀⠀⢸⣿⠀⠀⠀⣾⠋⠘⣷⠀⠀⠀⠀
// ⠀⠹⣿⡿⠿⢿⣦⡀⠀⠈⡙⠛⠒⠚⣟⠀⣸⠛⠛⢻⡀⠀⠀⠀⠀⢹⣿⡀⠀⠀⠀⠀⣼⡟⠀⢀⣀⣘⣓⣚⣧⣶⣶⣶⠖
// ⠀⠀⢸⣷⠀⠀⢿⣷⣠⣾⢿⣆⠀⠀⣿⠀⢻⡄⠀⠸⣧⣄⡀⠀⣀⣼⡿⠁⠀⠀⠀⣰⣿⢣⡾⠛⠉⠉⠛⣿⠋⢀⣿⠏⠀
// ⠀⠀⢸⣿⠀⠀⠈⢿⣿⠁⠈⣿⠀⢸⡏⣀⡼⣿⣄⠀⠈⠛⠿⠿⠟⠋⠁⠀⠀⢀⣼⡿⠃⠏⣀⣀⠀⠀⠀⠀⠀⣼⡿⠀⠀
// ⠀⠀⠀⣿⡀⠀⠀⠀⠁⠀⣸⡏⠴⠟⠛⠉⠀⠈⠻⢿⣦⣤⣄⣀⣀⣀⣠⣤⣶⣿⠋⠀⠀⢿⠏⠙⠻⢶⣦⣴⡾⠟⠁⠀⠀
// ⠀⠀⠀⠘⣿⣄⣶⡄⢀⣴⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠛⠛⠛⠛⠛⠉⠀⢹⠀⠀⠀⢀⣤⣶⣶⣶⣦⣄⡀⠀⠀⠀⠀
// ⠀⣠⡶⠋⠁⠈⠉⠁⠉⠉⠓⢦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠀⣴⡿⠋⠁⠀⠀⠉⠛⢿⣆⠀⠀⠀
// ⢰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⡏⢀⣾⡟⠁⠀⠀⠀⠀⠀⠀⠈⣿⡆⠀⠀
// ⣾⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢷⣄⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⣀⣴⠟⣠⣾⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⢹⣇⠀⠀
// ⢻⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣷⣤⣀⠀⣀⣀⣡⣤⡶⢟⣫⣵⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⡏⠀⠀
// ⠈⢿⣧⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠛⠿⠶⠶⣶⡶⠿⠿⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⡟⠁⠀⠀
// ⠀⠀⠙⢻⣷⣦⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣧⠈⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣴⠿⠋⠀⠀⠀⠀
// ⠀⠀⠀⠀⠈⠉⠛⠻⠿⣶⣶⣤⣄⣀⠀⠀⠀⠀⠀⣀⣼⡏⠀⠻⣧⣤⣀⠀⠀⢀⣠⠤⠤⠶⠶⠞⠛⠋⠁⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠙⠛⠿⣶⣤⡀⠀⠀⠙⣿⡆⠀⠈⢹⣯⠀⠈⠓⠲⣦⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⡆⠀⠀⢹⣷⠀⠀⠈⢿⣧⣀⠀⠀⠈⠛⣷⣶⠖⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢈⡿⠀⢀⣾⡏⠀⠀⠀⠀⠙⠻⢿⣷⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣞⣁⣤⡾⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀
#define ll long long
#define pb push_back
#define pb1 pop_back
#define ain int a[n]; for(int i = 0; i < n; i++) cin >> a[i];
// #define v(n) vector<int>v(n)
#define cy cout << "Yes" << endl;
#define cn cout << "No" << endl;
#define cY cout << "YES" << endl;
#define cN cout << "NO" << endl;
#define mp make_pair
#define ff first
#define ss second
 int arnold(vector<vector<int>>& dp, int n, int a[], int i , int cnt ) {
        if (n==0  && cnt>=2) {
            return 1;  
        }
        if(i<0 || n<0) return 0 ; 
        if (dp[i][n] != -1) return dp[i][n];

        int nottake = arnold(dp, n, a, i - 1 , cnt);  // Case when we do not take a[i]
        int take = 0;

        if (a[i] <= n) {
            // Recursive case: take a[i] and solve for the remaining value (n - a[i])
            int result = arnold(dp, n - a[i], a, i , cnt+1);
            take = a[i] * result;
        }

        return dp[i][n] = max(take, nottake);  // Take the max of the two choices
    }
    int integerBreak(int n) {
        int a[n] ;
        for(int i =0 ; i<n ; i++) a[i] = i+1; 
        vector<vector<int>>dp(n+ 1 , vector<int>(n+1 , -1)) ;  
        return arnold(dp , n , a , n-1, 0) ;
    }
};
8100