l=il=il=i としたときの合計金額の制約による rrr の右端 rv,ir_{v,i}rv,iと、種類数の制約による rrr の左端 rk,ir_{k,i}rk,i が全ての lll について求まれば、その差分を足し合わせたものが答えになるのでこの問題が解けます。
これは尺取り法によってそれぞれまとめて O(N)O(N)O(N) で求められるので、全体で O(N)O(N)O(N) で解くことが出来ます。