3妹：2哥，聽說你今天發(fā)工資啦？ 請(qǐng)我吃飯?jiān)趺礃?#xff0c;嘿嘿
2哥 : 切，你上周還發(fā)工資了呢，也沒見你請(qǐng)我吃飯。
3妹：哎呀， 我的工資都用來雙11 shopping了， 雙11過后我都吃了1周土了， 好2哥，就請(qǐng)我吃頓肉吧。
2哥 : 3妹，花錢要有節(jié)制啊，雙11雖然有一點(diǎn)優(yōu)惠，但也不能無節(jié)制的購物啊。
3妹：衣服、包包、零食，一看到都很便宜，就沒忍住，嘿嘿
2哥：你這開銷也太大了！看你可憐的份上，就請(qǐng)你吃頓肉吧。 下個(gè)月發(fā)工資記得請(qǐng)回來哈。
3妹：好滴好滴，2哥最好了。
2哥 : 但是有個(gè)條件，說到最大開銷，吃飯前我們要做一個(gè)關(guān)于最大開銷的題目，做出來我才請(qǐng)客。
3妹：沒問題，有吃的就有動(dòng)力！

題目：

給你一個(gè)下標(biāo)從 0 開始大小為 m * n 的整數(shù)矩陣 values ，表示 m 個(gè)不同商店里 m * n 件不同的物品。每個(gè)商店有 n 件物品，第 i 個(gè)商店的第 j 件物品的價(jià)值為 values[i][j] 。除此以外，第 i 個(gè)商店的物品已經(jīng)按照價(jià)值非遞增排好序了，也就是說對(duì)于所有 0 <= j < n - 1 都有 values[i][j] >= values[i][j + 1] 。

每一天，你可以在一個(gè)商店里購買一件物品。具體來說，在第 d 天，你可以：

選擇商店 i 。
購買數(shù)組中最右邊的物品 j ，開銷為 values[i][j] * d 。換句話說，選擇該商店中還沒購買過的物品中最大的下標(biāo) j ，并且花費(fèi) values[i][j] * d 去購買。
注意，所有物品都視為不同的物品。比方說如果你已經(jīng)從商店 1 購買了物品 0 ，你還可以在別的商店里購買其他商店的物品 0 。

請(qǐng)你返回購買所有 m * n 件物品需要的 最大開銷 。

示例 1：

輸入：values = [[8,5,2],[6,4,1],[9,7,3]]
輸出：285
解釋：第一天，從商店 1 購買物品 2 ，開銷為 values[1][2] * 1 = 1 。
第二天，從商店 0 購買物品 2 ，開銷為 values[0][2] * 2 = 4 。
第三天，從商店 2 購買物品 2 ，開銷為 values[2][2] * 3 = 9 。
第四天，從商店 1 購買物品 1 ，開銷為 values[1][1] * 4 = 16 。
第五天，從商店 0 購買物品 1 ，開銷為 values[0][1] * 5 = 25 。
第六天，從商店 1 購買物品 0 ，開銷為 values[1][0] * 6 = 36 。
第七天，從商店 2 購買物品 1 ，開銷為 values[2][1] * 7 = 49 。
第八天，從商店 0 購買物品 0 ，開銷為 values[0][0] * 8 = 64 。
第九天，從商店 2 購買物品 0 ，開銷為 values[2][0] * 9 = 81 。
所以總開銷為 285 。
285 是購買所有 m * n 件物品的最大總開銷。
示例 2：

輸入：values = [[10,8,6,4,2],[9,7,5,3,2]]
輸出：386
解釋：第一天，從商店 0 購買物品 4 ，開銷為 values[0][4] * 1 = 2 。
第二天，從商店 1 購買物品 4 ，開銷為 values[1][4] * 2 = 4 。
第三天，從商店 1 購買物品 3 ，開銷為 values[1][3] * 3 = 9 。
第四天，從商店 0 購買物品 3 ，開銷為 values[0][3] * 4 = 16 。
第五天，從商店 1 購買物品 2 ，開銷為 values[1][2] * 5 = 25 。
第六天，從商店 0 購買物品 2 ，開銷為 values[0][2] * 6 = 36 。
第七天，從商店 1 購買物品 1 ，開銷為 values[1][1] * 7 = 49 。
第八天，從商店 0 購買物品 1 ，開銷為 values[0][1] * 8 = 64 。
第九天，從商店 1 購買物品 0 ，開銷為 values[1][0] * 9 = 81 。
第十天，從商店 0 購買物品 0 ，開銷為 values[0][0] * 10 = 100 。
所以總開銷為 386 。
386 是購買所有 m * n 件物品的最大總開銷。

提示：

1 <= m == values.length <= 10
1 <= n == values[i].length <= 10^4
1 <= values[i][j] <= 10^6
values[i] 按照非遞增順序排序。

思路：

排序，
把所有數(shù)合并在一起排序， 詳見代碼

java代碼：

class Solution {public long maxSpending(int[][] values) {int m = values.length, n = values[0].length;int[] a = new int[m * n];int i = 0;for (int[] row : values) {System.arraycopy(row, 0, a, i, n);i += n;}Arrays.sort(a);long ans = 0;for (i = 0; i < a.length; i++) {ans += (long) a[i] * (i + 1);}return ans;}
}