Minimum Recolor Cost for Pairs

You are given n items numbered 0 to n - 1 and k colors numbered 0 to k - 1. The integer array colors gives each item's initial color, and the array costs (of length k) gives the cost of repainting any one item to color u: costs[u]. An item that already has the target color costs nothing. Each item may be repainted at most once.

You are also given an array pairs, where each pairs[j] = [a, b] requires items a and b to have the same color after all repainting is done.

Return the minimum total repainting cost that satisfies every pair requirement.

Examples

Example 1

Input: colors = [0,1,1,2], costs = [2,3,10], pairs = [[0,1],[2,3]]
Output: 5
Explanation: Items 0 and 1 must match: repaint item 1 to color 0 (cost 2). Items 2 and 3 must match: repaint item 3 to color 1 (cost 3). Total 2 + 3 = 5.

Example 2

Input: colors = [0,1], costs = [100,100,1], pairs = [[0,1]]
Output: 2
Explanation: Repainting either item to the other's color costs 100. It is cheaper to repaint both items to color 2 at cost 1 each, for a total of 2.