423. Battle
Time limit per test: 0.75
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
There are
n cities on a small island, numbered 1 through
n. Some pairs of cities are connected with bidirectional roads. All the cities were independent. All the cities lived in harmony with each other.
One day two cities
s and
t decided to create their own countries and conquer some of the other independent cities. We'll denote the country started by city
s as the first country, and the country started by city
t as the second country.
Suppose some day the first country contains cities from
A = {
a_{1},...,
a_{ka}} and the second country contains cities from
B = {
b_{1},...,
b_{kb}}. We define
neigh(
A) as set of cities connected with some city from
A by a road, but not from
A itself (so
). We also define
popul(
i) as the population of city
i, and
.
The first country can conquer a set
C of independent cities at once iff
In a similar manner the second country can conquer the set
C at once iff
.
In the morning of each day the first country can conquer some cities, and in the evening the second country can conquer some cities.
The first country wants to conquer the cities in such a way that in the end
popul(
A) 
popul(
B) is maximal possible, and the second country wants to conquer the cities in such a way that in the end
popul(
B) 
popul(
A) is maximal possible.
Input
The first line contains three positive integers
n,
s and
t (3 ≤
n ≤ 13, 1 ≤
s,
t ≤
n,
s ≠
t). Next
n lines contain
n characters each, with the
jth character in the
ith of those lines being '
1
' if cities
i and
j are connected by a road, and '
0
' otherwise. The next line contains
n integers
popul(
i) (
) — the populations of all cities.
Output
Output the final value of
popul(
A) 
popul(
B) assuming that both countries act optimally.
Example(s)
sample input

sample output

5 1 2
00111
00001
10010
10101
11010
12 100 5 5 7

85

sample input

sample output

3 1 3
010
101
010
5 5 11

11

sample input

sample output

7 1 5
0100011
1010001
0101001
0010100
0001000
1000001
1110010
90 20 20 10 200 85 80

85
