you can easily find the solution with O(nk^3)

but it will give u tle

after optimization with cumulative sum array it will be O(nk^2)