式を変形すると、

\(\begin{aligned} \sum_{i=1}^N\sum_{j=1}^M\max(A_i,B_j)(A_i+B_j)&=\sum_{i=1}^N\Bigg(\sum_{B_j\le A_i}A_i(A_i+B_j)+\sum_{B_j>A_i}B_j(A_i+B_j)\Bigg)\\&=\sum_{i=1}^N\Bigg({A_i}^2\sum_{B_j\le A_i}1+A_i\sum_{j=1}^MB_j+\sum_{B_j>A_i}{B_j}^2\Bigg) \end{aligned}\)

となります。これは、 \(B\) を昇順にソートし、累積和と二分探索を用いて高速に計算できます。

計算量は、 \(O((N+M)\log M)\) です。