Problem Description

Let S be a string of length 2*N, where each character in S is assigned an integer as its weight. The weight of a subsequence T of S, denoted by weight(T), is defined as the sum of all its characters’ weights. Your task is to divide S into two subsequences T1 and T2, each of length N, such that:
1.T1 is equal to T2.
2.|weight(T1) – weight(T2)| is as small as possible.

Input

The input contains multiple test cases.
Each case consists of three lines.

The first line contains an integer N (1<=N<=20).
The second line is a string S of length 2*N. Each character in S is either ‘a’ or ‘b’. The third line contains 2*N positive integers, where the ith integer is the weight of the ith character in S. No integer exceeds 1000000.

The input is terminated by N = 0.

Output

For each case, output the smallest difference between weight(T1) and weight(T2) in a line. If it is impossible to divide S into two equal subsequence, output -1 instead.

2
abab
3 1 10 5
3
aaabbb
1 1 1 2 2 2
3
abaaba
4 6 5 10 3 4
0

11
-1
2

Author

SYSU