--- Day 25: The Multiverse Machine ---

"This is incredible!" exclaims an elf physicist, showing you an ancient device recovered from deep within the North Pole ice. "We've discovered what appears to be a quantum computer from a long-lost civilization!"

"We need your help," the elf continues. "We're trying to transport quantum particles through these parallel universes, but these universes behave strangely - they expand and contract as we move between them!"

The rules of quantum transport are very strict:

• Each parallel universe starts as an NxN grid.
• There are many parallel universes, each with a distinct cycle length.
• Moving to an adjacent cell within the same universe costs 1 energy.
• You can choose to remain at the current cell, but it still costs 1 energy to do so.
• Jumping between universes when cycles align costs 10 energy.
• When you jump from Universe A to Universe B:
  • Universe A's grid shrinks by 1 in both dimensions.
  • If Universe B hasn't been visited before, its grid grows by 1 in both dimensions.
  • If any universe's grid becomes smaller than 2x2, it resets to its original NxN size and is no longer considered visited.
  • If a universe's cycle length aligns with the current cycle length but the grid is too small to jump to from your current position, a jump is impossible.

The elves need to transport a quantum particle from the starting position (0, 0) to a specific target location using the minimum energy.

Example:

2 7,8
4 5
6 8
9 3

In this example:

• The target point is at (7, 8) in Universe 2.

For Universe 1:

• Its cycle length is 4.
• Its initial dimensions are 5x5.

For Universe 2:

• Its cycle length is 6.
• Its initial dimensions are 8x8.

For Universe 3:

• Its cycle length is 9.
• Its initial dimensions are 3x3.

Universes 1 and 2 will align at 12 steps.
Universes 2 and 3 will align at 18 steps.
Universes 1 and 3 will align at 36 steps.

All three universes will align at 36 steps.

Your starting point is (0, 0) in Universe 1.

Following these rules:

• Universe 1 is too small to reach the target position directly, so your best choice is to move to (4, 4) using 5 energy and wait for 7 energy until you can jump to Universe 2.
• At this point, you should use 10 energy to jump to Universe 2.
• Universe 1 shrinks to 4x4, and Universe 2 grows to 9x9. Now you can move from (4, 4) to (7, 8) in 7 energy to reach your target point.

Your final energy usage will be 5 + 7 + 10 + 7 = 29

Remember, when jumping between universes:

• If you jump from Universe 1 (initially at 5x5) to Universe 2 (initially at 8x8), Universe 1 shrinks to become 4x4 and Universe 2 becomes 9x9.
• If you jump back from Universe 2 (now at 9x9) to Universe 1 (now at 4x4), Universe 2 shrinks to become 8x8 again, but Universe 1 remains at 4x4, because it has already been visited before.
• If Universe 3 (initially at 3x3) shrinks to 1x1, it would reset back to 3x3, and it is not considered visited anymore.

The elves are waiting anxiously. Can you help them optimize their quantum particle transport system while managing these expanding and contracting universes?