from typing import List

class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        n, m = len(skill), len(mana)

        # Prefix sums S[i] = sum_{k=0..i} skill[k]
        S = [0] * n
        run = 0
        for i, v in enumerate(skill):
            run += v
            S[i] = run

        if m == 1:
            return S[-1] * mana[0]
        if n == 1:
            return skill[0] * sum(mana)

        # Points for CHT: P_i = (S_i, -S_{i-1}) for i=0..n-1 with S_{-1}=0
        pts = [(S[0], 0)]
        for i in range(1, n):
            pts.append((S[i], -S[i-1]))

        # Build the UPPER hull (x increasing, y non-increasing)
        def cross(o, a, b):
            return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])

        hull = []
        for p in pts:
            while len(hull) >= 2 and cross(hull[-2], hull[-1], p) >= 0:
                hull.pop()
            hull.append(p)

        def dot(p, a, b):
            return p[0]*a + p[1]*b  # = S_i*a - S_{i-1}*b

        # On this hull, dot with q=(a,b) is unimodal → binary search the maximum
        def max_dot(a, b):
            lo, hi = 0, len(hull) - 1
            while lo < hi:
                mid = (lo + hi) // 2
                if dot(hull[mid], a, b) <= dot(hull[mid + 1], a, b):
                    lo = mid + 1
                else:
                    hi = mid
            return dot(hull[lo], a, b)

        # Base time: last potion through last wizard
        total = S[-1] * mana[-1]
        # Minimal gaps between consecutive potions
        for j in range(1, m):
            total += max_dot(mana[j - 1], mana[j])

        return total