<p>There are some robots and factories on the X-axis. You are given an integer array <code>robot</code> where <code>robot[i]</code> is the position of the <code>i<sup>th</sup></code> robot. You are also given a 2D integer array <code>factory</code> where <code>factory[j] = [position<sub>j</sub>, limit<sub>j</sub>]</code> indicates that <code>position<sub>j</sub></code> is the position of the <code>j<sup>th</sup></code> factory and that the <code>j<sup>th</sup></code> factory can repair at most <code>limit<sub>j</sub></code> robots.</p>

<p>The positions of each robot are <strong>unique</strong>. The positions of each factory are also <strong>unique</strong>. Note that a robot can be <strong>in the same position</strong> as a factory initially.</p>

<p>All the robots are initially broken; they keep moving in one direction. The direction could be the negative or the positive direction of the X-axis. When a robot reaches a factory that did not reach its limit, the factory repairs the robot, and it stops moving.</p>

<p><strong>At any moment</strong>, you can set the initial direction of moving for <strong>some</strong> robot. Your target is to minimize the total distance traveled by all the robots.</p>

<p>Return <em>the minimum total distance traveled by all the robots</em>. The test cases are generated such that all the robots can be repaired.</p>

<p><strong>Note that</strong></p>

<ul>
	<li>All robots move at the same speed.</li>
	<li>If two robots move in the same direction, they will never collide.</li>
	<li>If two robots move in opposite directions and they meet at some point, they do not collide. They cross each other.</li>
	<li>If a robot passes by a factory that reached its limits, it crosses it as if it does not exist.</li>
	<li>If the robot moved from a position <code>x</code> to a position <code>y</code>, the distance it moved is <code>|y - x|</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/15/example1.jpg" style="width: 500px; height: 320px;" />
<pre>
<strong>Input:</strong> robot = [0,4,6], factory = [[2,2],[6,2]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> As shown in the figure:
- The first robot at position 0 moves in the positive direction. It will be repaired at the first factory.
- The second robot at position 4 moves in the negative direction. It will be repaired at the first factory.
- The third robot at position 6 will be repaired at the second factory. It does not need to move.
The limit of the first factory is 2, and it fixed 2 robots.
The limit of the second factory is 2, and it fixed 1 robot.
The total distance is |2 - 0| + |2 - 4| + |6 - 6| = 4. It can be shown that we cannot achieve a better total distance than 4.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/15/example-2.jpg" style="width: 500px; height: 329px;" />
<pre>
<strong>Input:</strong> robot = [1,-1], factory = [[-2,1],[2,1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> As shown in the figure:
- The first robot at position 1 moves in the positive direction. It will be repaired at the second factory.
- The second robot at position -1 moves in the negative direction. It will be repaired at the first factory.
The limit of the first factory is 1, and it fixed 1 robot.
The limit of the second factory is 1, and it fixed 1 robot.
The total distance is |2 - 1| + |(-2) - (-1)| = 2. It can be shown that we cannot achieve a better total distance than 2.
</pre>

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

<ul>
	<li><code>1 &lt;= robot.length, factory.length &lt;= 100</code></li>
	<li><code>factory[j].length == 2</code></li>
	<li><code>-10<sup>9</sup> &lt;= robot[i], position<sub>j</sub> &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= limit<sub>j</sub> &lt;= robot.length</code></li>
	<li>The input will be generated such that it is always possible to repair every robot.</li>
</ul>

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        robot.sort()
        factory.sort()

        robotCount, factoryCount = len(robot), len(factory)

        prefixSum = [0]
        for _, limit in factory:
            prefixSum.append(prefixSum[-1] + limit)
        prefixSum = prefixSum[1:]

        # We create a table with robotCount rows and factoryCount columns
        # 	to be populated such that table[r][c] will denote the
        # 	minimum travelling distance of sending the r+1 leftmost robots to 
        #	the c+1 leftmost factories
        # Each table entry is initialized to None
        # If the c+1 leftmost factories cannot support the r+1 leftmost robots,
        # 	table[r][c] will be assigned -1
        table = [[None] * factoryCount for _ in range(robotCount)]

        def computeMin(numRobots, numFactories):
            # Any number of factories can support 0 robots; distance travelled is 0
            if numRobots == 0: return 0  		
            # 0 factories cannot support a nonzero amount of robots
            if numFactories == 0: return -1	
            # Note: we can now assume numRobots, numFactories > 0	

            robotIdx, factoryIdx = numRobots-1, numFactories-1

            # If the minimum travelling distance of the leftmost numRobots robots to the 
            # 	leftmost numFactories factories has already been computed, return it
            if table[robotIdx][factoryIdx] is not None: return table[robotIdx][factoryIdx]
            
            # If the leftmost numFactories factories cannot support the leftmost numRobots robots,
            #   we assign the corresponding table entry -1 to denote this
            if numRobots > prefixSum[factoryIdx]: 
                table[robotIdx][factoryIdx] = -1
                return computeMin(robotCount, factoryCount)

            # We've confirmed that the leftmost numFactories factories CAN support 
            # 	the leftmost numRobots robots, so we proceed by computing the 
            # 	minimum travelling distance
            runningMinimum = None
            currentDistance = 0
            rightmostFactoryLocation, rightmostFactoryLimit = factory[factoryIdx]

            # This loop works with two groups of factories:
            # 		1. The numFactories-th factory (the rightmost factory being considered)
            # 		2. All factories to the left of the numFactories-th factory
            # At the end of each loop, currentDistance will reflect the total distance 
            # 	travelled after sending the rightmost numSendRight robots to the 
            # 	rightmost factory
            # Depending on the capacity of the rightmost factory and how many robots 
            # 	need service, we compute the total travelling distance of assigning 
            # 	incrementally more robots closest to the rightmost factory 
            # 	(until it reaches capacity or no more robots need service)
            # 	and the remaining robots to the factories to the left of it,
            # 	all while tracking the minimum

            for numSendRight in range(1+min(numRobots, rightmostFactoryLimit)):
                numSendLeft = numRobots - numSendRight
                tempDistance = computeMin(numSendLeft, numFactories-1)

                if tempDistance != -1:
                    totalDistanceTravelled = tempDistance + currentDistance
                    if runningMinimum is None or runningMinimum > totalDistanceTravelled:
                        runningMinimum = totalDistanceTravelled

                currentDistance += abs(robot[numSendLeft-1] - rightmostFactoryLocation)

            table[robotIdx][factoryIdx] = runningMinimum

            return table[robotIdx][factoryIdx]

        return computeMin(robotCount, factoryCount)
1339