Migrated from Lutece 1608 暑假集训

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

一年一度的暑假集训又开始了，经历了一个月的个人训练，共有$N$（$N$为$3$的倍数）名选手突出重围，进入到了二轮的组队训练。组队训练是三个人组成一队进行比赛，所以$N$名队员将被组成$\frac{N}{3}$只队伍进行训练。$p(i,j,k)$表示队员$i$，队员$j$和队员$k$组成一队的配合度。队员的编号为$1$~$N$.现在，杨$sir$了解到了任意三名队员组队的配合度，他想采取一种组队方式，使$\frac{N}{3}$支队伍的配合度总和最高，请问最大的配合度总和为多少？

Input

第一行为一个整数$N$，代表进入二轮训练的人数。$(3 \leq N \leq 21)$

接下来$\frac{N(N-1)(N-2)}{6}$行，每行四个整数，$i,j,k,p(i,j,k)$，分别代表队员$i$，队员$j$和队员$k$和他们三人组成一队的配合度。

$(1 \leq i<j<k \leq N,1 \leq p(i,j,k) \leq 100)$

三名队员编号按照字典序从小到大的顺序进行输入。

Output

一个整数，$\frac{N}{3}$支队伍最大的配合度总和。

Samples

3
1 2 3 100

100

6
1 2 3 5
1 2 4 100
1 2 5 10
1 2 6 95
1 3 4 15
1 3 5 90
1 3 6 20
1 4 5 85
1 4 6 25
1 5 6 80
2 3 4 30
2 3 5 75
2 3 6 35
2 4 5 70
2 4 6 40
2 5 6 65
3 4 5 45
3 4 6 60
3 5 6 50
4 5 6 55

150

Note

样例$2$，杨$sir$会让队员$1$，队员$2$和队员$4$组成一队，配合度为$100$；队员$3$，队员$5$，队员$6$组成一队，配合度为$50$.最大的配合度总和为$100+50=150.$

Resources

2017 UESTC Training for Dynamic Programming