18666번 - AtCoder Quality Problem 다국어

You have a set S of n elements. You want to paint each subset of S either red or blue. For each subset s of S, you know that the cost to paint it red is R_s, and the cost to paint it blue is B_s.

Note: you want to paint subsets, not the elements.

There is only one requirement:

• If a and b are two subsets of S of the same color, the subset a ∪ b has the same color as a and b.

Find the minimum total cost to paint all 2ⁿ subsets.

The first line contains a single integer n (0 ≤ n ≤ 20), the number of elements.

The second line contains 2ⁿ integers R₀, R₁, . . . , R_2ⁿ−1 (−10⁹ ≤ R_i ≤ 10⁹), the costs to paint subsets red.

The third line contains 2ⁿ integers B₀, B₁, . . . , B_2ⁿ−1 (−10⁹ ≤ B_i ≤ 10⁹), the costs to paint subsets blue.

The subset i (0 ≤ i < 2ⁿ) is a subset consisting of elements j such that the j-th bit in the binary representation of i is 1.

Print one integer: the minimum cost to paint all subsets.