Objective

Give practice with recursion in C$.$

Give practice with a combinations style algorithm in C$.$

Story

Your coworkers at the KAT Pet Shop are furiously working at catching all the elephants and

placing the new baits. In lighter news the $3$ families that have been fostering cats now want to

permanently adopt a group of them. The only problem is that they want to adopt the same group

of cats.

You are here to mediate by determining which cats will go to which family. Some cats are cozier

in certain houses, and some cats will increase or decrease the coziness of other cats that wind

up in the same house. Luckily, you have knowledge of exactly how much each cat affects the

coziness of each other cat, and how much each family affects the coziness of each cat.

Each family will need to have at least $1$ cat, and each cat will be adopted out to $1$ of the $3$

families. We are interested in $2$ metrics,

$1.$ The coziness sum across all cats

$2.$ The coziness of the least cozy cat

Problem

You will be given the number of cats, the initial coziness for each family for each cat, and the

amount of coziness that each cat will change for each other cat based on their presence within

the same family.

Input

The input will begin with a single integer, N $(3<=$ N $<=15),$ representing the number of cats. The

next N lines each contain $3$ integers, the i$-$th line represents the coziness the i$-$th cat will start

with at each of the corresponding families. This value could be negative.

Following this will be N lines that each contain N integers. The i$-$th integer on the j$-$th line

represents the amount of coziness the j$-$th cat will change by $($positive is an increase and

negative is a decrease$),$ if the i$-$th cat is adopted by the same family as the j$-$th cat. The

diagonal will always be $0.$ That is the i$-$th cat will not affect its own coziness value.

You are guaranteed that each coziness value will be in the range of $[-1000,1000].$

Output

Print $2$ integers on a single line. The first integer should be the maximum coziness sum possible

and the second integer should be the coziness of the least cozy cat when assigning the cats

such that the least cozy cat is as cozy as possible.