Minimize total factory cost with distance penalties

You must choose construction options for factories to minimize a total cost.

Input format:

• options[i] is a list of options for factory i .
• Each option is a pair [cost, distance] .

For 3 factories, an example input is:

options = [
  [[10, 0], [20, 0], [35, 0]],
  [[35, 0], [50, 0], [25, 0]],
  [[30, 0], [5, 0], [40, 0]]
]

Total cost (for N factories)

If you pick exactly one option per built factory, define:

• Build cost = sum of chosen cost .
• Distance penalty = sum over adjacent built factories of abs(distance[i] - distance[i+1]) .

Total = build cost + distance penalty.

Questions

1. 3 factories, ignore distance : All distances are 0 (or distance penalties are ignored). Compute the minimum possible total cost.
2. 3 factories, include distance : Use the full total cost formula. Compute the minimum.
3. N factories, include distance : Generalize to any N factories. Compute the minimum efficiently.
4. N factories, must skip exactly one factory : You must choose options for exactly N-1 factories, skipping (not building) exactly one factory. Distance penalty applies between adjacent built factories in their original order (i.e., skipping connects its neighbors). Compute the minimum.

Output

Return the minimum total cost (and optionally the chosen options if requested).

Constraints / Notes

• Assume N and number of options per factory can be large enough that brute force over all combinations may be too slow.
• Discuss time/space complexity tradeoffs.