<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:
        # If all elements are the same, no cost is needed
        if len(set(nums)) <= 1:
            return 0
        
        # Prepare the data
        n = len(nums)
        num_cost_pairs = [(nums[i], cost[i]) for i in range(n)]
        num_cost_pairs.sort()
        
        # Precompute cumulative product costs and cumulative costs
        prod_costs = [0] * (n+1)
        pre_costs = [0] * (n+1)
        
        for i in range(n):
            prod_costs[i] = num_cost_pairs[i][0] * num_cost_pairs[i][1] + (prod_costs[i-1] if i > 0 else 0)
            pre_costs[i] = num_cost_pairs[i][1] + (pre_costs[i-1] if i > 0 else 0)
        
        # Print intermediate values for debugging
        # print('Sorted num-cost pairs:', num_cost_pairs)
        # print('Cumulative product costs:', prod_costs)
        # print('Cumulative costs:', pre_costs)
        
        def get_costs(left: int, right: int) -> int:
            return prod_costs[right] - (prod_costs[left] if left > 0 else 0)
        
        def get_prods(left: int, right: int) -> int:
            return pre_costs[right] - (pre_costs[left] if left > 0 else 0)
        
        def calculate_cost(x: int, index: int) -> int:
            small_costs = get_costs(0, index)
            large_costs = get_costs(index, n - 1)
            small_prods = get_prods(0, index)
            large_prods = get_prods(index, n - 1)
            # print(x)
            # print(small_costs,large_costs)
            # print(small_prods,large_prods)
            return large_costs - small_costs + ( x * (small_prods - large_prods) )
        
        # Find the optimal value
        min_cost = float('inf')
        optimal_value = 0
        index = 0
        
        # for i in range(num_cost_pairs[0][0], num_cost_pairs[-1][0] + 1):
        j=0
        # for j in range(len(num_cost_pairs)):
        while j<len(num_cost_pairs):
            i=num_cost_pairs[j][0]
            while index < n and num_cost_pairs[index][0] <= i:
                index += 1
            # print('index:',index-1,num_cost_pairs[index-1],i)
            current_cost = calculate_cost(i, index-1)
            if current_cost < min_cost:
                min_cost = current_cost
                optimal_value = i
            # print(current_cost)
            # should=sum(abs(va - i) * c for va, c in num_cost_pairs)
            # print(should==current_cost,i,':',should)
            # print()
            j=max(j+1,index)
        
        # Print final results
        # print('Optimal value:', optimal_value)
        # print('Minimum cost:', min_cost)
        
        # Calculate and return the final cost
        # total_cost = sum(abs(va - optimal_value) * c for va, c in num_cost_pairs)
        return min_cost

375