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]