#include <bits/stdc++.h>

// Tabulation Approach:

int solveTab(string &a, string &b) {

    vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, 0));

    for (int i = a.size() - 1; i >= 0; i--) {

        for (int j = b.size() - 1; j >= 0; j--) {

            int ans = 0;

            // Case 1: Matching

            if (a[i] == b[j]) {

                ans = 1 + dp[i + 1][j + 1];

            }

            // Case 2: Not matching

            else {

                ans = 0 + max(dp[i + 1][j], dp[i][j + 1]);

            }

            dp[i][j] = ans;

        }

    }

    return dp[0][0];

}

int lcs(string s, string t) {

    return solveTab(s, t);

}

        int solveTab(vector<int>& prices, int fee){

        int n = prices.size();

        vector<vector<int>> dp(n+1, vector<int> (2, 0));

        for(int index = n-1; index >= 0; index--){

            for(int buy = 0; buy <= 1; buy++){

            //buy and sell conditions:

            int profit = 0;

            if(buy == 1){ //buy allowed

                profit = max((-prices[index] + dp[index+1][0]), (0 + dp[index+1][1]));

        }

            else{  //buy == 0 (not allowed)

                profit = max((prices[index] + dp[index+1][1] - fee), (0 + dp[index+1][0]));

        }

            dp[index][buy] = profit;

        }

    }

    return dp[0][1];

}

int maximumProfit(vector<int> &prices, int n, int fee){

    return solveTab(prices, fee);

}

#include <bits/stdc++.h> 

int maximumProfit(vector<int> &prices){

        int n = prices.size();

        int mini = prices[0];  //assumed to be BUY

        int profit = 0;

        for(int i = 1; i < n; i++){

            int diff = prices[i] - mini;  //profit = sell - buy (here mini is assumed to be BUY)

            profit = max(profit, diff);

            mini = min(mini, prices[i]);

        }

    return profit;

}

long long int solve(int n, vector<long long int> &dp){

    //base case:

    if(n <= 1){

        return 1;

    }

    if(dp[n] != -1){

        return dp[n];

    }

    long long int ans = 0;

    // i -> is a root node here:

    for(int i = 1; i <= n; i++){

        ans +=  solve(i-1, dp) * solve(n-i, dp);

    }

    return dp[n] = ans;

} 

long long int numTrees(int n) {

    vector<long long int> dp(n+1, -1);

    return solve(n, dp);

}

#include <vector>

int solve(int dice, int face, int target, std::vector<std::vector<int>> &dp){

    //base case:

    if(target < 0){

        return 0;

    }

    if(dice == 0 && target != 0){

        return 0;

    }

    if(dice != 0 && dice == 0){

        return 0;

    }

    if(dice == 0 && target == 0){

        return 1;

    }

    if(dp[dice][target] != -1){

        return dp[dice][target];

    }

    int ans = 0;

    for(int i = 1; i <= face; i++){

        ans = (ans + solve(dice-1, face, target-i, dp)) % 1000000007;        

    }

    return dp[dice][target] = ans;

}

int diceThrows(int d, int f, int s) {

    std::vector<std::vector<int>> dp(d + 1, std::vector<int>(s + 1, -1));

    return solve(d, f, s, dp); 

}

#include <bits/stdc++.h> 

//Top - Down:

int solve(int index, int endIndex, vector<int> &arr, int k, vector<vector<int>> &dp){

        //base case:

        if(k == 0 || index > endIndex){

            return 0;

        }

        if(dp[index][k] != -1){

            return dp[index][k];

        }

        int eat = arr[index] + solve(index+2, endIndex, arr, k-1, dp);    //eat:

        int notEat = 0 + solve(index+1, endIndex, arr, k, dp);            //not eat:

    return dp[index][k] = max(eat, notEat);

}

int pizzaSharing(int n, vector<int> &arr){

    vector<vector<int>> dp1(n, vector<int> (n, -1));

    int case1 = solve(0, n-2, arr, n/3, dp1);

    vector<vector<int>> dp2(n, vector<int> (n, -1));

    int case2 = solve(1, n-1, arr, n/3, dp2);

    return max(case1, case2);

}

// (i) Recursion + Memoization:

int solveMem(vector<vector<int>> &MAT, int i, int j, int &maxi, vector<vector<int>> &dp){

    if (i >= MAT.size() || j >= MAT[0].size()) {

        return 0;

    }

    if(dp[i][j] != -1){

        return dp[i][j];

    }

    // Condition check to extend squares:

    int right = solveMem(MAT, i, j + 1, maxi, dp);

    int diagonal = solveMem(MAT, i + 1, j + 1, maxi, dp);

    int down = solveMem(MAT, i + 1, j, maxi, dp);

    // Current element is 1 (square can be formed):

    if (MAT[i][j] == 1) {

        dp[i][j] = 1 + min(right, min(diagonal, down));

        maxi = max(maxi, dp[i][j] * dp[i][j]); // Update with square of side length

        return dp[i][j];

    } else {

        return dp[i][j] = 0; // Square can't be formed

    }

}

// (ii) Tabultaion:

int solveTab(vector<vector<int>> &MAT, int &maxi){

    int row = MAT.size();

    int col = MAT[0].size();

    vector<vector<int>> dp(row+1, vector<int>(col+1, 0));

    for(int i = row-1; i >= 0; i--){

        for(int j = col-1; j >= 0; j--){

            // Condition check to extend squares:

            int right = dp[i][j+1];

            int diagonal = dp[i+1][j+1];

            int down = dp[i+1][j];

            // Current element is 1 (square can be formed):

            if (MAT[i][j] == 1) {

                dp[i][j] = 1 + min(right, min(diagonal, down));

                maxi = max(maxi, dp[i][j] * dp[i][j]); // Update with square of side length

            } 

            else{

                dp[i][j] = 0; // Square can't be formed

            }

        }

    }

    return dp[0][0];

}

int maximumAreaSquare(vector<vector<int>> &MAT, int n, int m){

    // Recursion + Memoization:

    // int maxi = 0;

    // vector<vector<int>> dp(n, vector<int> (m, -1));

    // solveMem(MAT, 0, 0, maxi, dp);

    // return maxi;

    // Tabulation:

    int maxi = 0;

    solveTab(MAT, maxi);

    return maxi;

}

int solveTab(int n){

        vector<int> dp(n+1, INT_MAX);

        //base case:

        dp[0] = 0;

        for(int i = 1; i <= n; i++){

            for(int j = 1; j*j <= n; j++){

                if(i - j*j >= 0){

                dp[i] = min(dp[i], 1 + dp[i - j*j]);

                }

            }

        }

    return dp[n];

}

int minCount(int n){

    return solveTab(n);

}

#include <bits/stdc++.h>

// 1) Top - Down: (Recursion + Memoization)

// int solve(vector<int> &nums, int n, vector<int> &dp){

//     //base case:

//     if(n < 0){

//         return 0;

//     }

//     if(n == 0){

//         return nums[0];

//     }

//     if(dp[n] != -1){

//         return dp[n];

//     }

//     int include = solve(nums, n-2, dp) + nums[n];

//     int exclude = solve(nums, n-1, dp) + 0;

//     dp[n] = max(include, exclude);

//     return dp[n];

// }

// int maximumNonAdjacentSum(vector<int> &nums){

//     int n = nums.size();

//     vector<int> dp(n, -1);

//     return solve(nums, n-1, dp);

// }

// 2) Bottom - Up: (Tabulation)

int solve(vector<int> &nums){

    int n = nums.size();

    vector<int> dp(n, 0);

    dp[0] = nums[0];

    for(int i = 1; i < n; i++){

        int include = dp[i-2] + nums[i];

        int exclude = dp[i-1] + 0;

        dp[i] = max(include, exclude);

    }

    return dp[n-1];

}

int maximumNonAdjacentSum(vector<int> &nums){

    return solve(nums);

}

#include <bits/stdc++.h> 

// TOP - DOWN: (Recursion + Memoization)

int solveMem(vector<int> &num, int x, vector<int> &dp){

    //base case:

    if(x == 0){

        return 0;

    }

    if(x < 0){

        return INT_MAX;

    }

    if(dp[x] != -1){

        return dp[x];

    }

    int mini = INT_MAX;

    for(int i = 0; i < num.size(); i++){

        int ans = solveMem(num, x - num[i], dp);

        if(ans != INT_MAX){

            mini = min(mini, 1+ans);

        }

    }

    dp[x] = mini;

    return mini;

}

int minimumElements(vector<int> &num, int x){

    vector<int> dp(x+1, -1);

    int ans = solveMem(num, x, dp);

    if(ans == INT_MAX){

        return -1;

    }

    else{

        return ans;

    }

}