Codah Club연습하고, 제출하고, 성장하세요.
로그인
한국어
#0000AE

Coolest Party

Juan has a birthday is coming up and he hasn't made up his mind about who he will invite. Unfortunately for him (and you), not all his friends get along with each other. Therefore in order to avoid any conflict Juan must invite a subset of his friends such that all possible pairs of invited friends get along with each other.



Naturally, some people are more fun than others, so Juan has determined everyone's fun level and wants to use it wants to maximize the amount of "fun" in his party.



Help Juan decide by finding the value of the optimal fun party he can have.



InputThe first line of the standard input contains the number 1<N<=15, where N corresponds to the number of possible friends Juan can invite. In the next N lines the first number is the fun level (0< Fi <=100) of the i-th person followed by a summary of that person's relationship with all of Juan's friends. "1" means friendly, while "0" means hostile. The j-th position in the summary will correspond to Juan's j-th friend.


OutputTo the standard output print the maximum net fun that Juan's party can obtain.



Input:
3
2 1 0 1
4 0 1 0
3 1 0 1
Output:
5


Here Juan has 3 friends with fun levels of 2, 4 , 3 respectively. Friends F1 & F3 get along while F2 doesn't get along with anybody (except himself). The optimal pick for Juan would be F1 & F3 which have net fun of 2+3 = 5.





Input:
5
2 1 0 1 1 0
3 0 1 0 1 1
2 1 0 1 1 0
1 1 1 1 1 0
3 0 1 0 0 1
Output:
6


Even though Juan can invite F1 , F3 , and F4 . All three of them combined are not as fun as just F2 and F5 .

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.