Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem G: 三队-杭州-划分字符串

Problem G: 三队-杭州-划分字符串

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 36  Solved: 8
[Submit][Status][Web Board]

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.

Sample Input

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

Sample Output

11
-1
2

HINT

[Submit][Status][Web Board]