<p>There are <code>n</code> <strong>piles</strong> of coins on a table. Each pile consists of a <strong>positive number</strong> of coins of assorted denominations.</p>

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

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/11/09/e1.png" style="width: 600px; height: 243px;" />
<pre>
<strong>Input:</strong> piles = [[1,100,3],[7,8,9]], k = 2
<strong>Output:</strong> 101
<strong>Explanation:</strong>
The above diagram shows the different ways we can choose k coins.
The maximum total we can obtain is 101.
</pre>

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

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

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

<ul>
	<li><code>n == piles.length</code></li>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= piles[i][j] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= sum(piles[i].length) &lt;= 2000</code></li>
</ul>

from itertools import accumulate
import heapq
from math import inf

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        """
        100 1 3
        7 8 9

        100 101 104
        7 15 24


        5 12 16


        4
        1 3
        2 2
        3 1
        """
        n = len(piles)

        dp = dict()
        for i in range(n):
            dp[(i,i)] = [0] + list(accumulate(piles[i][:min(k, len(piles[i]))]))

        total_n_of_nums = sum([len(lst) for lst in dp.values()])

        if total_n_of_nums == k:
            return sum([lst[-1] for lst in dp.values()])

        stack = [(0, n - 1)]
        visits = []
        while len(stack):
            i, j = stack.pop()
            if i == j:
                continue
            visits.append((i, j))
            mid = (i + j) // 2
            stack.append((i, mid))
            stack.append((mid+1, j))

        while len(visits):
            i, j = visits.pop()
            mid = (i + j) // 2

            left_l = len(dp[(i,mid)])
            right_l = len(dp[(mid+1, j)])

            curr_sum = 0

            if (i, j) not in dp:
                dp[(i,j)] = [0] * (min(k+1, left_l + right_l+1))

            l = len(dp[(i, j)])
            
            if i == 0 and j == n - 1:
                min_r = k
            else:
                min_r = 1

            for r in range(min_r, l):
                for t in range(min(left_l-1, r), -1, -1):
                    left_max = dp[(i, mid)][t]
                    if r - t >= right_l:
                        break

                    right_max = dp[(mid+1, j)][r - t]
                
                    curr_sum = max(curr_sum, left_max + right_max)
            
                dp[(i,j)][r] = curr_sum

                if curr_sum == 0:
                    break
            
        return dp[(0, n-1)][k]

        



        def find(i,j, remaining_k):
            if remaining_k == 0:
                return 0

            if i == j:
                return 0 if len(prefix_sum[i]) < remaining_k else prefix_sum[i][remaining_k-1]

            if remaining_k in dp.get((i,j), dict()):
                return dp[(i,j)][remaining_k]
  
            mid = (i + j) // 2
            curr_sum = 0

            for t in range(remaining_k+1):
                left_max = find(i, mid, t)
                right_max = find(mid+1, j, remaining_k - t)
            
                curr_sum = max(curr_sum, left_max + right_max)

            dp[(i,j)] = dp.get((i, j), dict())
            dp[(i,j)][remaining_k] = curr_sum

            return curr_sum

        # res = find(0, n-1, k)

        # print(dp.keys())

        # return res



        
1797