Maximum Affinity (Region Distribution with Pair Rules)

Given affinity[n] (n even) and m rules; each rule (x, y) says "if either index x or y is chosen for a region in one step, the other must be chosen for the opposite region in the next step." Maximize total affinity assigned to regionA over alternating steps (A first).

Constraints

• 2 ≤ n ≤ 10⁵, n even.
• -10⁹ ≤ affinity[i] ≤ 10⁹
• 1 ≤ m ≤ n/2