F. Walk in the Park
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice has started a dog walking service to earn a little extra income! She is able to walk up to 2 dogs a day, 7 days a week. Luckily, Alice has a lot of friends with dogs who need them to be walked on different days of the week and are willing to pay different amounts of money for the job to be completed. Alice has a list of $$$N$$$ friends, who need their dog to be walked for 0 to 7 days of the week. Alice can not choose the same job twice, as her friends only have one dog each. Can you help Alice determine the maximum amount of money she can make a week?

Input

The first line contains an integer $$$N\ (1 \leq N \leq 100)$$$ the number of friends Alice has.

The next $$$N$$$ lines will have eight integers each: the first seven integers will represent the days of the week; a 1 will indicate that the dog needs to be walked on that day and a 0 will indicate the dog does not need to be walked on that day. The eigth integer will be the amount of money, $$$m\ (1 \leq m \leq 10^5)$$$ that the job pays.

Output

Output one integer representing the maximum amount of money Alice can make in a week

Example
Input
4
1 0 1 0 1 0 1 10
0 1 0 1 0 1 0 5
1 1 1 1 1 1 1 100
1 0 0 0 0 0 0 100
Output
205