Seaside Shopping
本题没有可用的提交语言。
Description
Yolanda frequently goes shopping at a jellyfish-themed shop on a bustling oceanfront promenade. This week is the Jellyfish Lantern Festival, and she is excited to buy a few gifts for her friends.
There are $N$ items at the shop, labeled 1 to $N$. For the next 10 days, labeled from 1 to 10, you are given the stock of the items, $F$, where $F_{i,j} = 1$ if item $i$ is in stock on day $j$ and $F_{i,j} = 0$ if it is out of stock on day $j$. Note that $1 \leq i \leq N$ and $1 \leq j \leq 10$.
Let $c_i$ be the number of days during which item $i$ is in stock and Yolanda visits the store. To evaluate her selections, Yolanda applies a unique strategy. For integers $a$ and $b$, the beauty is equal to the output of $XOR\_range(a,b)$ where $XOR\_range(a,b)$ calculates the exclusive OR of the numbers between $a$ and $b$ inclusive. Given the array $P$, Yolanda has decided that the total beauty of all her purchases will be $XOR\_range(P_{1}, P_{c_1}) + XOR\_range(P_{2},P_{c_2}) + \cdots + XOR\_range(P_{N},P_{c_N})$.
On each day, Yolanda decides whether or not she will visit the shop. Find the maximum possible beauty of Yolanda's purchase when she decides whether to visit the shop on each of the 10 days.
The first line has an integer $N$ for $(1\leq N \leq 100)$.
The next $N$ lines contain the array $F$ where $0 \leq F_{i,j} \leq 1$,
$F_{1,1} \: F_{1,2} \: \cdots \: F_{1,10}$
$\vdots$
$F_{N,1} \: F_{N,2} \: \cdots \: F_{N,10}$
The next line contains the array $P$ where $0 \leq P_{i,j} \leq 10^9$,
$P_{0} \: \cdots \: P_{\max\{10,N\}}$
Please print the maximum possible beauty of Yolanda's purchases.
Input
The first line has an integer $N$ for $(1\leq N \leq 100)$.
The next $N$ lines contain the array $F$ where $0 \leq F_{i,j} \leq 1$,
$F_{1,1} \: F_{1,2} \: \cdots \: F_{1,10}$
$\vdots$
$F_{N,1} \: F_{N,2} \: \cdots \: F_{N,10}$
The next line contains the array $P$ where $0 \leq P_{i,j} \leq 10^9$,
$P_{0} \: \cdots \: P_{\max\{10,N\}}$
Output
Please print the maximum possible beauty of Yolanda's purchases.
1
0 0 0 1 1 1 0 1 0 1
0 3 0 0 0 8 0 0 0 0 0
2
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1
0 10 9 8 7 6 5 4 3 2 1
11
21
Note
In the first test sample, it would be optimal for Yolanda to visit the first shop on all the days where the item is in stock. Then the answer is $XOR\_range(P_1, P_5) = XOR\_range(3, 8) = 11$.
In the second sample, note the arguments of $XOR\_range$ may be unordered.