Algorithms
Hard
2931
3107
Maximum Spending After Buying Items
maximum-spending-after-buying-items
"""
You are given a 0-indexed m * n integer matrix values, representing the values of m * n different items in m different shops. Each shop has n items where the jth item in the ith shop has a value of values[i][j]. Additionally, the items in the ith shop are sorted in non-increasing order of value. That is, values[i][j] >= values[i][j + 1] for all 0 <= j < n - 1.

On each day, you would like to buy a single item from one of the shops. Specifically, On the dth day you can:

 * Pick any shop i.
 * Buy the rightmost available item j for the price of values[i][j] * d. That is, find the greatest index j such that item j was never bought before, and buy it for the price of values[i][j] * d.

Note that all items are pairwise different. For example, if you have bought item 0 from shop 1, you can still buy item 0 from any other shop.

Return the maximum amount of money that can be spent on buying all m * n products.

Example 1:

Input: values = [[8,5,2],[6,4,1],[9,7,3]]
Output: 285
Explanation: On the first day, we buy product 2 from shop 1 for a price of values[1][2] * 1 = 1.
On the second day, we buy product 2 from shop 0 for a price of values[0][2] * 2 = 4.
On the third day, we buy product 2 from shop 2 for a price of values[2][2] * 3 = 9.
On the fourth day, we buy product 1 from shop 1 for a price of values[1][1] * 4 = 16.
On the fifth day, we buy product 1 from shop 0 for a price of values[0][1] * 5 = 25.
On the sixth day, we buy product 0 from shop 1 for a price of values[1][0] * 6 = 36.
On the seventh day, we buy product 1 from shop 2 for a price of values[2][1] * 7 = 49.
On the eighth day, we buy product 0 from shop 0 for a price of values[0][0] * 8 = 64.
On the ninth day, we buy product 0 from shop 2 for a price of values[2][0] * 9 = 81.
Hence, our total spending is equal to 285.
It can be shown that 285 is the maximum amount of money that can be spent buying all m * n products.

Example 2:

Input: values = [[10,8,6,4,2],[9,7,5,3,2]]
Output: 386
Explanation: On the first day, we buy product 4 from shop 0 for a price of values[0][4] * 1 = 2.
On the second day, we buy product 4 from shop 1 for a price of values[1][4] * 2 = 4.
On the third day, we buy product 3 from shop 1 for a price of values[1][3] * 3 = 9.
On the fourth day, we buy product 3 from shop 0 for a price of values[0][3] * 4 = 16.
On the fifth day, we buy product 2 from shop 1 for a price of values[1][2] * 5 = 25.
On the sixth day, we buy product 2 from shop 0 for a price of values[0][2] * 6 = 36.
On the seventh day, we buy product 1 from shop 1 for a price of values[1][1] * 7 = 49.
On the eighth day, we buy product 1 from shop 0 for a price of values[0][1] * 8 = 64
On the ninth day, we buy product 0 from shop 1 for a price of values[1][0] * 9 = 81.
On the tenth day, we buy product 0 from shop 0 for a price of values[0][0] * 10 = 100.
Hence, our total spending is equal to 386.
It can be shown that 386 is the maximum amount of money that can be spent buying all m * n products.


Constraints:

 * 1 <= m == values.length <= 10
 * 1 <= n == values[i].length <= 104
 * 1 <= values[i][j] <= 106
 * values[i] are sorted in non-increasing order.
"""
class Solution:
    def maxSpending(self, values: List[List[int]]) -> int:
        
You are given a 0-indexed m * n integer matrix values, representing the values of m * n different items in m different shops. Each shop has n items where the jth item in the ith shop has a value of values[i][j]. Additionally, the items in the ith shop are sorted in non-increasing order of value. That is, values[i][j] >= values[i][j + 1] for all 0 <= j < n - 1.

On each day, you would like to buy a single item from one of the shops. Specifically, On the dth day you can:

 * Pick any shop i.
 * Buy the rightmost available item j for the price of values[i][j] * d. That is, find the greatest index j such that item j was never bought before, and buy it for the price of values[i][j] * d.

Note that all items are pairwise different. For example, if you have bought item 0 from shop 1, you can still buy item 0 from any other shop.

Return the maximum amount of money that can be spent on buying all m * n products.

Example 1:

Input: values = [[8,5,2],[6,4,1],[9,7,3]]
Output: 285
Explanation: On the first day, we buy product 2 from shop 1 for a price of values[1][2] * 1 = 1.
On the second day, we buy product 2 from shop 0 for a price of values[0][2] * 2 = 4.
On the third day, we buy product 2 from shop 2 for a price of values[2][2] * 3 = 9.
On the fourth day, we buy product 1 from shop 1 for a price of values[1][1] * 4 = 16.
On the fifth day, we buy product 1 from shop 0 for a price of values[0][1] * 5 = 25.
On the sixth day, we buy product 0 from shop 1 for a price of values[1][0] * 6 = 36.
On the seventh day, we buy product 1 from shop 2 for a price of values[2][1] * 7 = 49.
On the eighth day, we buy product 0 from shop 0 for a price of values[0][0] * 8 = 64.
On the ninth day, we buy product 0 from shop 2 for a price of values[2][0] * 9 = 81.
Hence, our total spending is equal to 285.
It can be shown that 285 is the maximum amount of money that can be spent buying all m * n products.

Example 2:

Input: values = [[10,8,6,4,2],[9,7,5,3,2]]
Output: 386
Explanation: On the first day, we buy product 4 from shop 0 for a price of values[0][4] * 1 = 2.
On the second day, we buy product 4 from shop 1 for a price of values[1][4] * 2 = 4.
On the third day, we buy product 3 from shop 1 for a price of values[1][3] * 3 = 9.
On the fourth day, we buy product 3 from shop 0 for a price of values[0][3] * 4 = 16.
On the fifth day, we buy product 2 from shop 1 for a price of values[1][2] * 5 = 25.
On the sixth day, we buy product 2 from shop 0 for a price of values[0][2] * 6 = 36.
On the seventh day, we buy product 1 from shop 1 for a price of values[1][1] * 7 = 49.
On the eighth day, we buy product 1 from shop 0 for a price of values[0][1] * 8 = 64
On the ninth day, we buy product 0 from shop 1 for a price of values[1][0] * 9 = 81.
On the tenth day, we buy product 0 from shop 0 for a price of values[0][0] * 10 = 100.
Hence, our total spending is equal to 386.
It can be shown that 386 is the maximum amount of money that can be spent buying all m * n products.


Constraints:

 * 1 <= m == values.length <= 10
 * 1 <= n == values[i].length <= 104
 * 1 <= values[i][j] <= 106
 * values[i] are sorted in non-increasing order.


Please complete the code below to solve above prblem:
```python
class Solution:
    def maxSpending(self, values: List[List[int]]) -> int:
        
```

my_solution = Solution()

test_input = { "values": [[8,5,2],[6,4,1],[9,7,3]] }
assert my_solution.maxSpending(**test_input) == 285

test_input = { "values": [[10,8,6,4,2],[9,7,5,3,2]] }
assert my_solution.maxSpending(**test_input) == 386

test_input = { "values": [[1000000]] }
assert my_solution.maxSpending(**test_input) == 1000000

test_input = { "values": [[1]] }
assert my_solution.maxSpending(**test_input) == 1

test_input = { "values": [[1],[2]] }
assert my_solution.maxSpending(**test_input) == 5

test_input = { "values": [[2],[1]] }
assert my_solution.maxSpending(**test_input) == 5

test_input = { "values": [[1],[1]] }
assert my_solution.maxSpending(**test_input) == 3

test_input = { "values": [[5,2]] }
assert my_solution.maxSpending(**test_input) == 12

test_input = { "values": [[5,5]] }
assert my_solution.maxSpending(**test_input) == 15

test_input = { "values": [[7,5]] }
assert my_solution.maxSpending(**test_input) == 19

test_input = { "values": [[3,2,1]] }
assert my_solution.maxSpending(**test_input) == 14

test_input = { "values": [[2,2,1]] }
assert my_solution.maxSpending(**test_input) == 11

test_input = { "values": [[3,3,2]] }
assert my_solution.maxSpending(**test_input) == 17

test_input = { "values": [[3],[2],[1]] }
assert my_solution.maxSpending(**test_input) == 14

test_input = { "values": [[2],[10],[1]] }
assert my_solution.maxSpending(**test_input) == 35

test_input = { "values": [[1000000,1000000,1000000]] }
assert my_solution.maxSpending(**test_input) == 6000000

test_input = { "values": [[1000000,1000000,1000000,1000000]] }
assert my_solution.maxSpending(**test_input) == 10000000

test_input = { "values": [[1000000],[1000000],[1000000],[1000000]] }
assert my_solution.maxSpending(**test_input) == 10000000

test_input = { "values": [[1000000,1000000],[1000000,1000000]] }
assert my_solution.maxSpending(**test_input) == 10000000

test_input = { "values": [[2,1],[4,3]] }
assert my_solution.maxSpending(**test_input) == 30

test_input = { "values": [[3,1],[4,2]] }
assert my_solution.maxSpending(**test_input) == 30

test_input = { "values": [[4,1],[3,2]] }
assert my_solution.maxSpending(**test_input) == 30

test_input = { "values": [[15,13,13,12,12,12,12,11,11,11,11,9,9,8,7,5,5,5,1]] }
assert my_solution.maxSpending(**test_input) == 2162

test_input = { "values": [[13,13,11,7,2,1],[13,10,10,6,3,3]] }
assert my_solution.maxSpending(**test_input) == 776

test_input = { "values": [[12,6],[13,5],[13,3],[6,6],[15,6],[5,4],[6,1]] }
assert my_solution.maxSpending(**test_input) == 971

test_input = { "values": [[15,15,14,14,14,10,10,9,9,8,8,8,7,7,7,4]] }
assert my_solution.maxSpending(**test_input) == 1585

test_input = { "values": [[11,10],[10,1],[14,6],[13,5],[7,3],[10,10],[10,5]] }
assert my_solution.maxSpending(**test_input) == 1061

test_input = { "values": [[15,13,12,7,6,4,1]] }
assert my_solution.maxSpending(**test_input) == 298

test_input = { "values": [[8,2],[4,1],[10,4]] }
assert my_solution.maxSpending(**test_input) == 133

test_input = { "values": [[10,4],[13,2],[7,5],[15,11]] }
assert my_solution.maxSpending(**test_input) == 380

test_input = { "values": [[13,10,10,9,8,5,5,2,1,1]] }
assert my_solution.maxSpending(**test_input) == 465

test_input = { "values": [[15,14,8,7,5,5,1]] }
assert my_solution.maxSpending(**test_input) == 283

test_input = { "values": [[15,15,14,14,14,14,13,11,10,10,10,9,7,7,6,6,4,4,2,1]] }
assert my_solution.maxSpending(**test_input) == 2449

test_input = { "values": [[15,14,11,10,10,6,2],[13,8,8,6,6,3,2]] }
assert my_solution.maxSpending(**test_input) == 1084

test_input = { "values": [[15,15,14,13,13,12,11,9,9,9,8,6,5,5,4,3,2,1,1]] }
assert my_solution.maxSpending(**test_input) == 2030

test_input = { "values": [[15,10,7],[14,2,2],[14,13,12],[13,13,10]] }
assert my_solution.maxSpending(**test_input) == 975

test_input = { "values": [[10,9,3,3],[11,8,7,2],[14,14,13,1],[14,14,11,4],[13,11,9,5]] }
assert my_solution.maxSpending(**test_input) == 2338

test_input = { "values": [[11,7,5,2],[15,5,5,3]] }
assert my_solution.maxSpending(**test_input) == 307

test_input = { "values": [[15,10,10,9,8,7,4,2,2]] }
assert my_solution.maxSpending(**test_input) == 425

test_input = { "values": [[15,13,12,12,10,5,4,3,1]] }
assert my_solution.maxSpending(**test_input) == 484

test_input = { "values": [[12,12,12,11,10,10,7,7,6,5,5,3,2,1]] }
assert my_solution.maxSpending(**test_input) == 979

test_input = { "values": [[15,13,13,13,12,12,11,11,10,9,9,9,8,6,6,4,4,3,2,1]] }
assert my_solution.maxSpending(**test_input) == 2253

test_input = { "values": [[14,11],[11,8],[10,4],[4,3],[9,6],[8,4],[7,7],[10,4],[14,4]] }
assert my_solution.maxSpending(**test_input) == 1621

test_input = { "values": [[14,13,13,11,11,8,8,7,6,4,3,2,1]] }
assert my_solution.maxSpending(**test_input) == 912

test_input = { "values": [[15,14,14,10,10,9,9,7,7,7,7,7,6,6,6,4,4,3,3]] }
assert my_solution.maxSpending(**test_input) == 1823

test_input = { "values": [[14,13,11,10,10,1,1],[15,12,8,6,6,5,5]] }
assert my_solution.maxSpending(**test_input) == 1120

test_input = { "values": [[15,14,13,12,11,10,10,10,9,7,6,6,4,3,3,3,2,2,1]] }
assert my_solution.maxSpending(**test_input) == 1860

test_input = { "values": [[12,6,5,4,2]] }
assert my_solution.maxSpending(**test_input) == 109

test_input = { "values": [[15,15,14,13,12,12,12,11,10,10,9,9,9,8,7,6,3,2]] }
assert my_solution.maxSpending(**test_input) == 2006

test_input = { "values": [[15,14,12,11,10,10,7,6,2,1]] }
assert my_solution.maxSpending(**test_input) == 610

test_input = { "values": [[15,13,12,11,8,6,5]] }
assert my_solution.maxSpending(**test_input) == 328

test_input = { "values": [[15,15,12,10,9,7,7,6,6,5,4,2,1]] }
assert my_solution.maxSpending(**test_input) == 896

test_input = { "values": [[15,15,12,12,10,10,9,7,6,4,4,4,1]] }
assert my_solution.maxSpending(**test_input) == 969

test_input = { "values": [[15,14,14,13,8,7,7,4,3,3,2,1]] }
assert my_solution.maxSpending(**test_input) == 792

test_input = { "values": [[15,15,14,14,14,13,10,8,6,6,5,5,3,3,2,2,1]] }
assert my_solution.maxSpending(**test_input) == 1634

test_input = { "values": [[14,12,11,10,10,8,7,7,5,5,3,3,3]] }
assert my_solution.maxSpending(**test_input) == 855

test_input = { "values": [[14,14,9,9,4,4,1],[12,12,9,8,7,6,3]] }
assert my_solution.maxSpending(**test_input) == 1060

test_input = { "values": [[15,15,15,13,12,12,10,9,9,9,9,7,6,4,4,4,1]] }
assert my_solution.maxSpending(**test_input) == 1727

test_input = { "values": [[9,4],[13,4],[13,9],[6,5],[8,2],[13,1]] }
assert my_solution.maxSpending(**test_input) == 732

test_input = { "values": [[14,9,9,9,8,7,5],[15,14,10,8,5,3,1]] }
assert my_solution.maxSpending(**test_input) == 1094

test_input = { "values": [[15,15,14,13,10,3,1]] }
assert my_solution.maxSpending(**test_input) == 354

test_input = { "values": [[13,12],[13,12],[11,8],[14,3]] }
assert my_solution.maxSpending(**test_input) == 441

test_input = { "values": [[13,12,11,10,7,5,5,1]] }
assert my_solution.maxSpending(**test_input) == 358

test_input = { "values": [[15,10,9,8,8,7,7,5,4,3,1]] }
assert my_solution.maxSpending(**test_input) == 582

test_input = { "values": [[10,10,6,4,1],[14,13,13,11,9],[14,11,7,4,3]] }
assert my_solution.maxSpending(**test_input) == 1302

test_input = { "values": [[15,14,12,12,11,11,10,9,9,8,8,6,6,4,2,2,1]] }
assert my_solution.maxSpending(**test_input) == 1596

test_input = { "values": [[12,5,4,3,3,2,1,1],[13,11,9,9,6,4,3,1]] }
assert my_solution.maxSpending(**test_input) == 1019

test_input = { "values": [[15,15,13,11,10,10,7,1,1]] }
assert my_solution.maxSpending(**test_input) == 526

test_input = { "values": [[14,12,10,4,3,1],[12,12,8,7,6,2],[15,13,8,5,4,1]] }
assert my_solution.maxSpending(**test_input) == 1719

test_input = { "values": [[13,8,8,8,5,4,3],[15,13,9,8,7,3,2]] }
assert my_solution.maxSpending(**test_input) == 1006

test_input = { "values": [[13,13,12,12,9]] }
assert my_solution.maxSpending(**test_input) == 186

test_input = { "values": [[10,3],[11,9],[10,5],[8,7],[6,1]] }
assert my_solution.maxSpending(**test_input) == 472

test_input = { "values": [[15,15,12,12,11,10,9,8,2,2,1,1,1]] }
assert my_solution.maxSpending(**test_input) == 941

test_input = { "values": [[14,14,13,13,11,11,10,10,10,9,8,8,7,7,6,6,5,4,3]] }
assert my_solution.maxSpending(**test_input) == 2023

test_input = { "values": [[11,10,9,7,6,5,3,1],[14,14,10,9,7,4,4,3]] }
assert my_solution.maxSpending(**test_input) == 1270

test_input = { "values": [[6,2],[10,2],[13,5],[8,7],[10,3],[13,2],[13,6]] }
assert my_solution.maxSpending(**test_input) == 972

test_input = { "values": [[15,15,15,14,13,12,6,5,5,4]] }
assert my_solution.maxSpending(**test_input) == 694

test_input = { "values": [[11,9],[8,1],[2,1],[15,13],[12,4],[14,5],[13,4]] }
assert my_solution.maxSpending(**test_input) == 1113

test_input = { "values": [[15,14,14,13,12,11,10,10,5,4,2]] }
assert my_solution.maxSpending(**test_input) == 800

test_input = { "values": [[13,12,12,6,5,5,4,2,2,2,1]] }
assert my_solution.maxSpending(**test_input) == 523

test_input = { "values": [[13,8],[15,1],[9,1],[13,1]] }
assert my_solution.maxSpending(**test_input) == 372

test_input = { "values": [[12,8,4,1],[14,8,8,3]] }
assert my_solution.maxSpending(**test_input) == 335

test_input = { "values": [[15,14,14,13,13,13,12,12,9,9,8,7,6,5,5,5,4,3,1]] }
assert my_solution.maxSpending(**test_input) == 2113

test_input = { "values": [[13,9,8,2,1],[9,4,3,2,1],[10,8,6,3,1]] }
assert my_solution.maxSpending(**test_input) == 877

test_input = { "values": [[8,6],[13,1],[12,8],[8,7]] }
assert my_solution.maxSpending(**test_input) == 342

test_input = { "values": [[9,7],[15,15],[9,8],[6,1],[11,4]] }
assert my_solution.maxSpending(**test_input) == 585

test_input = { "values": [[14,9,9,8,6,4,2]] }
assert my_solution.maxSpending(**test_input) == 257

test_input = { "values": [[15,13,11,11,10,9,5,5,4,4,4,4,3,2]] }
assert my_solution.maxSpending(**test_input) == 968

test_input = { "values": [[13,7,7,4],[8,8,6,6]] }
assert my_solution.maxSpending(**test_input) == 305

test_input = { "values": [[15,13,12,10,10,10,9,9,9,8,7,6,6,5,4,4,2,1,1]] }
assert my_solution.maxSpending(**test_input) == 1805

test_input = { "values": [[13,13,1],[11,5,4],[14,5,1],[15,5,2],[10,1,1],[15,12,1]] }
assert my_solution.maxSpending(**test_input) == 1714

test_input = { "values": [[15,15,14,14,11,10,10,8,8,8,3,1,1]] }
assert my_solution.maxSpending(**test_input) == 1050

test_input = { "values": [[3,3],[15,10],[14,9]] }
assert my_solution.maxSpending(**test_input) == 236

test_input = { "values": [[14,13,11,10,9,7,2]] }
assert my_solution.maxSpending(**test_input) == 314

test_input = { "values": [[11,7],[5,3],[11,6],[6,1],[15,13]] }
assert my_solution.maxSpending(**test_input) == 550

test_input = { "values": [[14,13,13,12,12,12,11,11,9,8,8,6,5,5,5,5,3,3,2]] }
assert my_solution.maxSpending(**test_input) == 1962

test_input = { "values": [[14,14,13,13,13,12,12,11,10,9,9,8,8,7,3,2,2]] }
assert my_solution.maxSpending(**test_input) == 1750

test_input = { "values": [[15,8],[12,2],[15,10],[9,3],[5,4],[14,2],[7,6]] }
assert my_solution.maxSpending(**test_input) == 1091

test_input = { "values": [[15,9,7,3,3],[7,6,4,3,2],[15,9,8,4,4],[15,10,9,7,4]] }
assert my_solution.maxSpending(**test_input) == 1952

test_input = { "values": [[12,12,10,8,8,8,8,6,2,2,1]] }
assert my_solution.maxSpending(**test_input) == 585