There are n piles of coins on a table. Each pile consists of a positive number of coins of assorted denominations.

In one move, you can choose any coin on top of any pile, remove it, and add it to your wallet.

Given a list piles, where piles[i] is a list of integers denoting the composition of the ith pile from top to bottom, and a positive integer k, return the maximum total value of coins you can have in your wallet if you choose exactly k coins optimally.

&nbsp;
Example 1:

Input: piles = [[1,100,3],[7,8,9]], k = 2
Output: 101
Explanation:
The above diagram shows the different ways we can choose k coins.
The maximum total we can obtain is 101.


Example 2:

Input: piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
Output: 706
Explanation:
The maximum total can be obtained if we choose all coins from the last pile.


&nbsp;
Constraints:


	n == piles.length
	1 &lt;= n &lt;= 1000
	1 &lt;= piles[i][j] &lt;= 105
	1 &lt;= k &lt;= sum(piles[i].length) &lt;= 2000


class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        n = len(piles)
        prefixSum = []
        for i in range(n):
            temp = [0]
            for j in range(len(piles[i])):
                temp.append(temp[-1] + piles[i][j])
            prefixSum.append(temp)
            
        dp = [[0] * (k + 1) for _ in range(n)]
        for j in range(1, k + 1):
            if j < len(prefixSum[0]):
                dp[0][j] = prefixSum[0][j]
        
        for i in range(1, n):
            for j in range(1, k + 1):
                for l in range(len(prefixSum[i])):
                    if l > j:
                        break
                    dp[i][j] = max(dp[i][j], prefixSum[i][l] + dp[i - 1][j - l])
        return dp[n - 1][k]
class Solution {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int n = piles.size();
        int[][] ans = new int[n+1][2001];
        Collections.sort(piles, (List<Integer> a, List<Integer> b) -> b.size() - a.size());
        for(int i = 1; i <= k; i++) {
            for(int j = 1; j <= n; j++) {
                int sizeOfPile = piles.get(j-1).size();
                List<Integer> pile = piles.get(j-1);
                int sum = 0;
                ans[j][i] = ans[j-1][i];
                for(int l = 1; l <= Math.min(i, sizeOfPile); l++) {
                    // Take K from this pile + remaining from previous piles
                    sum += pile.get(l-1);
                    int rem = i - l;
                    ans[j][i] = Math.max(ans[j][i], sum + ans[j-1][rem]);
                }
            }
        }

        return ans[n][k];
    }
}
class Solution {
public:
   int dp[1001][2001]; //Dp array For Memoization.
   int solve(vector<vector<int>>&v,int index,int coin)
   {
       if(index>=v.size()||coin==0) //Base Condition
           return 0;
       if(dp[index][coin]!=-1) //Check wheather It is Already Calculated Or not.
           return dp[index][coin];

       /* Our 1st choice :- We not take any Coin from that pile*/
       int ans=solve(v,index+1,coin); //Just Call function for next Pile.

       /*Otherwise we can take Coins from that Pile.*/
       int loop=v[index].size()-1;
       int sum=0;

       for(int j=0;j<=min(coin-1,loop);j++) //
       {
           sum=sum+v[index][j];
           ans=max(ans,sum+solve(v,index+1,coin-(j+1)));

           /*Aove we Pass coin-(j+1). Because till j'th index we have taken j+1 coin from that pile.*/
       }

       return dp[index][coin]=ans;
   }
   int maxValueOfCoins(vector<vector<int>>& piles, int k) {
       memset(dp,-1,sizeof(dp));
       return solve(piles,0,k);
   }
};
/**
 * @param {number[][]} piles
 * @param {number} k
 * @return {number}
 */
var maxValueOfCoins = function(piles, k) {
    var n = piles.length;
    var cache = {};
    
    var getMax = function(i, k) {
        if (i >= n || k <= 0) return 0;
        var key = i + ',' + k;
        if (cache[key] !== undefined) return cache[key];
        var ans = getMax(i + 1, k);
        var cur = 0;
        
        for (var j = 0; j < piles[i].length && j < k; j++) {
            cur+=piles[i][j];
            ans = Math.max(ans, cur + getMax(i + 1, k - j - 1));
        }
        
        return cache[key] = ans;
    }
    
    return getMax(0, k);
};
Maximum Value of K Coins From Piles