我们班最近要春游，有些人想和有些人在一块，所以有了下面这个题：

把 $n$ 个人平均分成 $k$ 组，有一些人是朋友，求一种分法，使得在同一组里的朋友对数总和最大。

对于 50% 的数据，保证 $k = 2$。

对于 100% 的数据，保证 $1 \le n \le 50$，$1 \le k \le 8$，$n$ 能被 $k$ 整除。

请问各位dalao有思路吗，或者这个问题是NP-Hard的？