class Solution(object):
    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [[0 for _ in range(n+1)]  for _ in range(n+1)]

        for gap in range(1,n):
            for lo in range(1, n+1-gap):
                hi = lo + gap
                dp[lo][hi] = min(x + max(dp[lo][x-1],dp[x+1][hi]) for x in range(lo,hi))

        return dp[1][n]



if __name__ == '__main__':
    s = Solution()
    a = s.kSmallestPairs([1,1,2],[1,2,3],2)    
    print(a)

80de80bf20d6205feb8961fb8f91e1e7b6f2b1cf
<mask token>

class Solution(object):
    <mask token>


<mask token>

class Solution(object):

    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [[(0) for _ in range(n + 1)] for _ in range(n + 1)]
        for gap in range(1, n):
            for lo in range(1, n + 1 - gap):
                hi = lo + gap
                dp[lo][hi] = min(x + max(dp[lo][x - 1], dp[x + 1][hi]) for
                    x in range(lo, hi))
        return dp[1][n]


<mask token>

class Solution(object):

    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [[(0) for _ in range(n + 1)] for _ in range(n + 1)]
        for gap in range(1, n):
            for lo in range(1, n + 1 - gap):
                hi = lo + gap
                dp[lo][hi] = min(x + max(dp[lo][x - 1], dp[x + 1][hi]) for
                    x in range(lo, hi))
        return dp[1][n]


if __name__ == '__main__':
    s = Solution()
    a = s.kSmallestPairs([1, 1, 2], [1, 2, 3], 2)
    print(a)

class Solution(object):
    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [[0 for _ in range(n+1)]  for _ in range(n+1)]

        for gap in range(1,n):
            for lo in range(1, n+1-gap):
                hi = lo + gap
                dp[lo][hi] = min(x + max(dp[lo][x-1],dp[x+1][hi]) for x in range(lo,hi))

        return dp[1][n]



if __name__ == '__main__':
    s = Solution()
    a = s.kSmallestPairs([1,1,2],[1,2,3],2)    
    print(a)
