這題很顯然是DP，有點像是2021年TOI初選的pC。

先說O(n*m)的解法好了，我們可以把他看成是一個二維空間中帶權重的點，DP[i][j]就代表選第i個超級石跟第j個鑰石的電池總能量最大值，可以很容易的觀察出DP[i][j]等於他這個點的左上角那塊區域的最大值。

講白一點就是DP[i][j] = max(DP[1~i-1][1~j-1])+a[i][j]，a[i][j]就是這個點的權重。然後答案就是這個DP表格中的最大值。

那取max的部份我們可以開一個表格紀錄，令mx[i][j] = max(DP[1~i][1~j]) = max(mx[i][j-1],mx[i-1][j])，這樣就不用再另外花時間去找左上角區域的最大值了。

可是這樣只能拿74%，所以我們要再進一步的去優化他。

我們先將序列照超級石的序號由小排到大，如果超級石相同就照鑰石由大排到小，DP[i]表示跟i配對的最大值，可以推得DP[i] = max(max(DP[1],DP[2],...,DP[i-1])+w,DP[i])//w代表他們之間配對會有多少能量。

為什麼會照這樣排序呢?原因很簡單，假設目前的超級石編號為x，鑰石編號為y，我們能選的只有1~x-1的超級石與1~y-1鑰石配對，所以如果我們y從大排到小，就可以避免前面的答案被修改掉導致後面的答案出錯 (滾動DP的概念)。

那要怎麼修改DP的值呢？單點修改線段樹，整體的時間複雜度為O(nlogm)

code： https://github.com/LJH-coding/code/blob/main/b903.cpp