CF321E Ciel and Gondolas

Fox Ciel 正在游乐园，现在她正在摩天轮前面排队。队伍中共有 $n$ 个人（准确来说是狐狸）：我们用第一个人指队伍最前面的人，用第 $n$ 个人指队伍最后一个人。 将有 $k$ 个座舱，分配座舱的方法如下： - 当第一个座舱到来时，队伍前面的 $q_1$ 个人进入座舱。 - 当第二个座舱到来时，剩下队伍的前面 $q_2$ 个人进入座舱。...... - 剩下的 $q_k$ 个人进入最后（第 $k$ 个）座舱。 注意，$q_1, q_2, ..., q_k$ 必须都是正整数。你可以从题意得出 $q_1 + q_2 + \cdots + q_k = n$，且 $q_i > 0$。 你知道，每个人都不愿和陌生人同舱，所以你的任务是找到一种最优分配方式（即找到一个最优的 $q$ 序列），使得大家都尽可能满意。对于每一对乘客 $i$ 和 $j$，存在一个值 $u_{ij}$ 表示他们之间的陌生程度。你可以假设对于所有的 $i, j$ 都有 $u_{ij} = u_{ji}$，且对于所有 $i$ 有 $u_{ii} = 0$，其中 $1 \leq i, j \leq n$。一个座舱的陌生值等于该座舱中所有两两乘客之间的陌生程度之和。 总陌生值等于所有座舱的陌生值之和。请你帮助 Fox Ciel 找到某种最优分配方式，使总陌生值的最小可能值是多少。

第一行为两个整数 $n$ 和 $k$（$1 \leq n \leq 4000$，$1 \leq k \leq \min(n, 800)$），分别表示排队人数和座舱数量。接下来的 $n$ 行，每行包含 $n$ 个整数，表示矩阵 $u$，其中 $0 \leq u_{ij} \leq 9$，且 $u_{ij} = u_{ji}$，$u_{ii} = 0$。 请使用高效的输入方式（例如，对于 Java 请使用 BufferedReader 而不是 Scanner）。

输出一个整数，表示最小可能的总陌生值。

在第一个样例中，可以这样分配：{1, 2} 进同一个座舱，{3, 4, 5} 进另一个座舱。 在第二个样例中，最优方案是：{1, 2, 3} | {4, 5, 6} | {7, 8}。 由 ChatGPT 5 翻译