<p>You are given two <strong>0-indexed</strong> arrays <code>nums</code> and <code>cost</code> consisting each of <code>n</code> <strong>positive</strong> integers.</p>

<p>You can do the following operation <strong>any</strong> number of times:</p>

<ul>
	<li>Increase or decrease <strong>any</strong> element of the array <code>nums</code> by <code>1</code>.</li>
</ul>

<p>The cost of doing one operation on the <code>i<sup>th</sup></code> element is <code>cost[i]</code>.</p>

<p>Return <em>the <strong>minimum</strong> total cost such that all the elements of the array </em><code>nums</code><em> become <strong>equal</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,5,2], cost = [2,3,1,14]
<strong>Output:</strong> 8
<strong>Explanation:</strong> We can make all the elements equal to 2 in the following way:
- Increase the 0<sup>th</sup> element one time. The cost is 2.
- Decrease the 1<sup><span style="font-size: 10.8333px;">st</span></sup> element one time. The cost is 3.
- Decrease the 2<sup>nd</sup> element three times. The cost is 1 + 1 + 1 = 3.
The total cost is 2 + 3 + 3 = 8.
It can be shown that we cannot make the array equal with a smaller cost.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,2,2,2,2], cost = [4,2,8,1,3]
<strong>Output:</strong> 0
<strong>Explanation:</strong> All the elements are already equal, so no operations are needed.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length == cost.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i], cost[i] &lt;= 10<sup>6</sup></code></li>
	<li>Test cases are generated in a way that the output doesn&#39;t exceed&nbsp;2<sup>53</sup>-1</li>
</ul>

class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        """
        In math, this problem is written as
        minimize_{k} sum_{i=0}^{n-1} abs(nums[i] - k) * cost[i],
        subject to the constraints that k is an integer and that
        min(nums) <= k <= max(nums).

        Note that cost is entrywise non-negative. Define the function
        f whose domain is real numbers, as
        f(k) = sum_{i=0}^{n-1} abs(nums[i] - k) * cost[i].
        Note that f is a continuous convex function of k.
        The interval [min(nums), max(nums)] is a compact set,
        so f achieves its minimum over this set. Let m be a
        minimizer, so that f(m) = min_{k in [min(nums), max(nums)]} f(k).
        We claim that m is also a global minimizer, so that
        f(m) = min_{k in reals} f(k). This follows simply from
        the fact that if we consider any x < min(nums), then
        f(x) > f(min(nums)) >= f(m), also that x > max(nums) implies
        f(x) > f(max(nums)) >= f(m).

        Now, note that f is non-strictly increasing as we move away from m.
        As a contradiction, assume f is decreasing over some
        interval as we move away from m. So there exists
        x < y < m by continuity such that f(x) < f(y), or x > y > m
        such that f(x) < f(y). Since both cases are symmetric, we
        consider the former. Note we could assume y < m due to
        continuity.

        Then note by the convexity of f, and the fact that
        y lies between x and m, that there exists t in [0,1]
        such that
        f(y) = f(t x + (1-t) m) <= t f(x) + (1-t) f(m)
        <= t f(x) + (1-t) f(x)
        = f(x)
        < f(y),
        where we used the fact that m is a minimizer of f.

        So we have arrived at a contradiction, and shown that
        f increases as we move away from the minimizer m. Indeed,
        we have shown this property true for any one dimensional
        continuous convex function.

        Now it should be intutive that we can minimize a continuous
        convex function, whose minimizer is known to lie in an
        interval, via binary search. The key is what condition to
        do binary search on. Via the fact we proved above, we know
        that if we are decreasing as we move right then we are to
        the left of m, and if we are increasing as we move right
        then we are to the right of m.

        So how do identify whether we are increasing or decreasing at
        a point? For a differentiable function, just take the derivative
        and see whether it is positive of negative!

        But our function f is not differentiable.

        However, notice that for the purposes of this problem,
        we only care about identifying the
        *integer* that minimizes f in the interval
        [min(nums), max(nums)]. So if we want to identify
        whether f is increasing or decreasing at a point x,
        just compare f(x) to f(x+1) and f(x-1). Then just binary search.

        I think you can actually show that m is an integer,
        but we don't need to do that.
        """
        n = len(nums)
        left, right = min(nums), max(nums)

        while left < right - 1:
            mid = (left + right) // 2
            a = self.evaluate(nums, cost, mid - 1)
            b = self.evaluate(nums, cost, mid)
            c = self.evaluate(nums, cost, mid + 1)

            if a <= b <= c:
                # increasing
                right = mid
            elif a >= b >= c:
                # decreasing
                left = mid
            else:
                # a >= b <= c
                # because b cannot be larger than max(a,c) due to convexity
                return b
        a = self.evaluate(nums, cost, left)
        b = self.evaluate(nums, cost, right)
        if a <= b:
            return a
        return b

    def evaluate(self, nums, cost, k):
        # returns the cost if all integers in nums are moved to k
        n = len(nums)
        res = 0
        for i in range(n):
            res += cost[i] * abs(k - nums[i])
        return res
732