Python Medium
```python3 []
class Solution:
    def maximumCoins(self, A: List[List[int]], k: int) -> int:
        '''
        try every l endpoint to the right and r endpoint to the left of exactly k size
        prefix sums

        (1, 2) (4, 5)
        '''

        A.sort()
        prev_end = 0
        for l, r, c in list(A):
            if l - 1 != prev_end:
                A.append([prev_end + 1, l - 1, 0])
            prev_end = r

        A.sort()

        best = 0
        cur_sum = 0
        cur_bags = 0
        q = deque()
        for l, r, c in A:
            interval_length = r - l + 1
            if interval_length + cur_bags <= k:
                cur_bags += interval_length
                q.append((l, r, c))
                cur_sum += interval_length * c

                if cur_bags == k:
                    best = max(best, cur_sum)
                

            else:
                cur_sum += interval_length * c
                cur_bags += interval_length
                q.append((l, r, c))

                while cur_bags > k:
                    diff = cur_bags - k
                    tmp_sum = cur_sum
                    tmp_sum -= diff * c
                    best = max(best, tmp_sum)

                    ll, rr, cc = q.popleft()
                    interval_length_2 = rr - ll + 1

                    cur_bags -= interval_length_2
                    cur_sum -= cc * interval_length_2

                if cur_bags == k:
                    best = max(best, cur_sum)
            
            best = max(best, cur_sum)

        B = []
        for l, r, c in A:
            B.append((-r, -l, c))

        B.sort()




        cur_sum = 0
        cur_bags = 0

        # print(B)
        q = deque()
        for r, l, c in B:
            r *= -1
            l *= -1
            interval_length = r - l + 1

            if interval_length + cur_bags <= k:
                cur_bags += interval_length
                q.append((l, r, c))
                cur_sum += interval_length * c

                best = max(best, cur_sum)
                

            else:
                cur_sum += interval_length * c
                cur_bags += interval_length
                q.append((l, r, c))

                

                while cur_bags > k:
                    # print(q, cur_sum, cur_bags)
                    diff = cur_bags - k
                    tmp_sum = cur_sum
                    tmp_sum -= diff * c
                    best = max(best, tmp_sum)

                    ll, rr, cc = q.popleft()
                    interval_length_2 = rr - ll + 1

                    cur_bags -= interval_length_2
                    cur_sum -= cc * interval_length_2

                if cur_bags == k:
                    best = max(best, cur_sum)



            best = max(best, cur_sum)


        return best
                        
                        

                


                

```
['Python3']