from functools import lru_cache
from itertools import accumulate
from typing import List


class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], lim: int) -> int:
        n = len(nums)
        dp = {}
        cum_sum = [0] + list(accumulate(nums))

        @lru_cache(None)
        def waste(i, j):
            if i >= j:
                return 0
            maximum = max(nums[e] for e in range(i,j))
            return maximum * (j - i) - cum_sum[j] + cum_sum[i]

        def helper(st, k):
            if k == 0:
                return waste(st, n)
            if (st, k) not in dp:
                dp[(st, k)] = min((waste(st, i + 1) + helper(i + 1, k - 1) for i in range(st, n)), default=0)
            return dp[(st, k)]

        return helper(0, lim)


if __name__ == '__main__':
    print(Solution().minSpaceWastedKResizing(
        [389034, 703056, 995498, 779239, 730317, 991926, 566433, 439487, 615871, 778326, 761895, 162030, 928424, 435038,
         686736, 103832, 874191, 513118, 645559, 427941, 984669, 997743, 293329, 34306, 723812, 388529, 227824, 464921,
         466298, 996730, 247583, 897005, 380304, 104181, 718988, 385179, 570914, 945498, 676150, 376097, 63492, 417480,
         289283, 199029, 128094, 995110, 889228, 864227, 476806, 96127, 694964, 222410, 672876, 670557, 626153, 22395,
         53036, 825014, 349710, 255401, 132041, 825207, 592003, 215174, 71943, 870128, 802326, 581129, 217221, 614868,
         226442, 852548, 911942, 244317, 344520, 811985, 154722, 826953, 944276, 624933, 2974, 290744, 900105, 151717,
         136307, 566457, 262830, 837303, 182974, 115267, 693170, 908537, 27033, 138206, 15583, 375645, 828359, 826731,
         249490, 617458, 339499, 16548, 182711, 278259, 54945, 132916, 777748, 441410, 551641, 119170, 781887, 66646,
         499381, 470051, 815810, 379626, 538170, 622504, 114352, 473963, 528314, 232312, 991341, 644987, 45472, 762570,
         821274, 952896, 909096, 690910, 546782, 316283, 480293, 674592, 32664, 63781, 502249, 888457, 421127, 446981,
         719426, 113207, 514085, 747007, 953891, 465109, 77061, 942950, 84715]
        , 116))

1473235545d12dfad1cc2dfb92f7da18005100df
<mask token>


class Solution:
    <mask token>


<mask token>

<mask token>


class Solution:

    def minSpaceWastedKResizing(self, nums: List[int], lim: int) ->int:
        n = len(nums)
        dp = {}
        cum_sum = [0] + list(accumulate(nums))

        @lru_cache(None)
        def waste(i, j):
            if i >= j:
                return 0
            maximum = max(nums[e] for e in range(i, j))
            return maximum * (j - i) - cum_sum[j] + cum_sum[i]

        def helper(st, k):
            if k == 0:
                return waste(st, n)
            if (st, k) not in dp:
                dp[st, k] = min((waste(st, i + 1) + helper(i + 1, k - 1) for
                    i in range(st, n)), default=0)
            return dp[st, k]
        return helper(0, lim)


<mask token>

<mask token>


class Solution:

    def minSpaceWastedKResizing(self, nums: List[int], lim: int) ->int:
        n = len(nums)
        dp = {}
        cum_sum = [0] + list(accumulate(nums))

        @lru_cache(None)
        def waste(i, j):
            if i >= j:
                return 0
            maximum = max(nums[e] for e in range(i, j))
            return maximum * (j - i) - cum_sum[j] + cum_sum[i]

        def helper(st, k):
            if k == 0:
                return waste(st, n)
            if (st, k) not in dp:
                dp[st, k] = min((waste(st, i + 1) + helper(i + 1, k - 1) for
                    i in range(st, n)), default=0)
            return dp[st, k]
        return helper(0, lim)


if __name__ == '__main__':
    print(Solution().minSpaceWastedKResizing([389034, 703056, 995498, 
        779239, 730317, 991926, 566433, 439487, 615871, 778326, 761895, 
        162030, 928424, 435038, 686736, 103832, 874191, 513118, 645559, 
        427941, 984669, 997743, 293329, 34306, 723812, 388529, 227824, 
        464921, 466298, 996730, 247583, 897005, 380304, 104181, 718988, 
        385179, 570914, 945498, 676150, 376097, 63492, 417480, 289283, 
        199029, 128094, 995110, 889228, 864227, 476806, 96127, 694964, 
        222410, 672876, 670557, 626153, 22395, 53036, 825014, 349710, 
        255401, 132041, 825207, 592003, 215174, 71943, 870128, 802326, 
        581129, 217221, 614868, 226442, 852548, 911942, 244317, 344520, 
        811985, 154722, 826953, 944276, 624933, 2974, 290744, 900105, 
        151717, 136307, 566457, 262830, 837303, 182974, 115267, 693170, 
        908537, 27033, 138206, 15583, 375645, 828359, 826731, 249490, 
        617458, 339499, 16548, 182711, 278259, 54945, 132916, 777748, 
        441410, 551641, 119170, 781887, 66646, 499381, 470051, 815810, 
        379626, 538170, 622504, 114352, 473963, 528314, 232312, 991341, 
        644987, 45472, 762570, 821274, 952896, 909096, 690910, 546782, 
        316283, 480293, 674592, 32664, 63781, 502249, 888457, 421127, 
        446981, 719426, 113207, 514085, 747007, 953891, 465109, 77061, 
        942950, 84715], 116))

from functools import lru_cache
from itertools import accumulate
from typing import List


class Solution:

    def minSpaceWastedKResizing(self, nums: List[int], lim: int) ->int:
        n = len(nums)
        dp = {}
        cum_sum = [0] + list(accumulate(nums))

        @lru_cache(None)
        def waste(i, j):
            if i >= j:
                return 0
            maximum = max(nums[e] for e in range(i, j))
            return maximum * (j - i) - cum_sum[j] + cum_sum[i]

        def helper(st, k):
            if k == 0:
                return waste(st, n)
            if (st, k) not in dp:
                dp[st, k] = min((waste(st, i + 1) + helper(i + 1, k - 1) for
                    i in range(st, n)), default=0)
            return dp[st, k]
        return helper(0, lim)


if __name__ == '__main__':
    print(Solution().minSpaceWastedKResizing([389034, 703056, 995498, 
        779239, 730317, 991926, 566433, 439487, 615871, 778326, 761895, 
        162030, 928424, 435038, 686736, 103832, 874191, 513118, 645559, 
        427941, 984669, 997743, 293329, 34306, 723812, 388529, 227824, 
        464921, 466298, 996730, 247583, 897005, 380304, 104181, 718988, 
        385179, 570914, 945498, 676150, 376097, 63492, 417480, 289283, 
        199029, 128094, 995110, 889228, 864227, 476806, 96127, 694964, 
        222410, 672876, 670557, 626153, 22395, 53036, 825014, 349710, 
        255401, 132041, 825207, 592003, 215174, 71943, 870128, 802326, 
        581129, 217221, 614868, 226442, 852548, 911942, 244317, 344520, 
        811985, 154722, 826953, 944276, 624933, 2974, 290744, 900105, 
        151717, 136307, 566457, 262830, 837303, 182974, 115267, 693170, 
        908537, 27033, 138206, 15583, 375645, 828359, 826731, 249490, 
        617458, 339499, 16548, 182711, 278259, 54945, 132916, 777748, 
        441410, 551641, 119170, 781887, 66646, 499381, 470051, 815810, 
        379626, 538170, 622504, 114352, 473963, 528314, 232312, 991341, 
        644987, 45472, 762570, 821274, 952896, 909096, 690910, 546782, 
        316283, 480293, 674592, 32664, 63781, 502249, 888457, 421127, 
        446981, 719426, 113207, 514085, 747007, 953891, 465109, 77061, 
        942950, 84715], 116))

from functools import lru_cache
from itertools import accumulate
from typing import List


class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], lim: int) -> int:
        n = len(nums)
        dp = {}
        cum_sum = [0] + list(accumulate(nums))

        @lru_cache(None)
        def waste(i, j):
            if i >= j:
                return 0
            maximum = max(nums[e] for e in range(i,j))
            return maximum * (j - i) - cum_sum[j] + cum_sum[i]

        def helper(st, k):
            if k == 0:
                return waste(st, n)
            if (st, k) not in dp:
                dp[(st, k)] = min((waste(st, i + 1) + helper(i + 1, k - 1) for i in range(st, n)), default=0)
            return dp[(st, k)]

        return helper(0, lim)


if __name__ == '__main__':
    print(Solution().minSpaceWastedKResizing(
        [389034, 703056, 995498, 779239, 730317, 991926, 566433, 439487, 615871, 778326, 761895, 162030, 928424, 435038,
         686736, 103832, 874191, 513118, 645559, 427941, 984669, 997743, 293329, 34306, 723812, 388529, 227824, 464921,
         466298, 996730, 247583, 897005, 380304, 104181, 718988, 385179, 570914, 945498, 676150, 376097, 63492, 417480,
         289283, 199029, 128094, 995110, 889228, 864227, 476806, 96127, 694964, 222410, 672876, 670557, 626153, 22395,
         53036, 825014, 349710, 255401, 132041, 825207, 592003, 215174, 71943, 870128, 802326, 581129, 217221, 614868,
         226442, 852548, 911942, 244317, 344520, 811985, 154722, 826953, 944276, 624933, 2974, 290744, 900105, 151717,
         136307, 566457, 262830, 837303, 182974, 115267, 693170, 908537, 27033, 138206, 15583, 375645, 828359, 826731,
         249490, 617458, 339499, 16548, 182711, 278259, 54945, 132916, 777748, 441410, 551641, 119170, 781887, 66646,
         499381, 470051, 815810, 379626, 538170, 622504, 114352, 473963, 528314, 232312, 991341, 644987, 45472, 762570,
         821274, 952896, 909096, 690910, 546782, 316283, 480293, 674592, 32664, 63781, 502249, 888457, 421127, 446981,
         719426, 113207, 514085, 747007, 953891, 465109, 77061, 942950, 84715]
        , 116))
