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 j^th item in the i^th shop has a value of values[i][j]. Additionally, the items in the i^th 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 d^th day you can:
- Pick any shop
i. - Buy the rightmost available item
jfor the price ofvalues[i][j] * d. That is, find the greatest indexjsuch that itemjwas never bought before, and buy it for the price ofvalues[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
285Buying the items in an order that assigns smaller values to earlier days and larger values to later days gives a maximum total spending of 285.
Example 2
Input
values = [[10,8,6,4,2],[9,7,5,3,2]]Output
386Buying all products optimally over ten days yields a maximum total spending of 386.
Constraints
- 1 <= m == values.length <= 10
- 1 <= n == values[i].length <= 10^4
- 1 <= values[i][j] <= 10^6
- values[i] are sorted in non-increasing order.