N が小さければ
https://codeforces.com/contest/1295/problem/F
とほぼ似た問題になって, O(N^4)とかで解ける
提出見てたらO(N^3) な解答もあるっぽい