← 返回题目列表

Codeforces · 431/B

B. 淋浴线

中文机器翻译题面 查看原题

许多学生住在宿舍里。宿舍是一个充满有趣的娱乐和可能性的全新世界,但它也有其缺点。

只有一个淋浴间,并且有多个学生希望早上洗澡。这就是为什么每天早上宿舍淋浴门前都会排起五人的队。淋浴间一打开,队伍中的第一个人就进入淋浴间。过了一会儿,第一个人离开淋浴间,下一个人进入淋浴间。这个过程一直持续到排队的每个人都洗完澡为止。

洗澡需要一些时间,所以排队的学生边等边说话。在每个时刻,学生们都成对说话:队列中的第 (2i - 1) 个人(当前时刻)与第 (2i) 个人交谈。

让我们更详细地看看这个过程。让我们将人员编号为 1 到 5。假设该行最初看起来为 23154(2 号人员位于该行的开头)。然后,在淋浴开始之前,2与3交谈,1与5交谈,4不与任何人交谈。然后2进入淋浴间。 2 号洗澡,3 号和 1 号说话,5 号和 4 号也说话。然后,3进入淋浴间。 3 洗澡时,1 和 5 说话,4 不和任何人说话。然后 1 进入淋浴间,当他在那里时,5 和 4 聊天。然后5进入淋浴,然后4进入淋浴。

我们知道,如果学生 i 和 j 说话,那么第 i 个学生的幸福感会增加 gij,第 j 个学生的幸福感会增加 gji。你的任务是找到队列中学生的初始顺序,使得最终所有学生的总幸福感最大。请注意,有些学生可能会进行多次演讲。在上面的示例中,学生 1 和 5 在等待淋浴打开时交谈,而学生 3 则在淋浴。

输入

输入由五行组成,每行包含五个空格分隔的整数:第 i 行中的第 j 个数字显示 gij (0 ≤ gij ≤ 105)。保证所有 i 的 gii = 0。

假设学生编号为 1 到 5。

输出

打印一个整数——学生的最大可能总幸福感。

示例

输入 #1

0 0 0 0 9
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
7 0 0 0 0

输出 #1

32

输入 #2

0 43 21 18 2
3 0 21 11 65
5 2 0 1 4
54 62 12 0 99
87 64 81 33 0

输出 #2

620

注意

在第一个样本中,行的最佳排列是 23154。在这种情况下,总幸福度等于:

(g23 + g32 + g15 + g51) + (g13 + g31 + g54 + g45) + (g15 + g51) + (g54 + g45) = 32