← 返回题目列表

Codeforces · 463/C

C. 加加里和主教

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

Gargari 嫉妒他的朋友 Caisa 赢得了上一题的比赛。他想要证明自己是一个天才。

他有一个 n × n 的棋盘。棋盘的每个方格上都写有一个数字。 Gargari 想要将两个主教放置在棋盘上,使得没有任何单元格受到他们两个的攻击。考虑一个写有数字 x 的牢房,如果该牢房受到其中一位主教的攻击,加加里将获得 x 美元。告诉加加里,如何在棋盘上放置主教以获得最大的金钱。

如果某个单元格与主教位于同一对角线上,我们假设该单元格受到了主教的攻击(主教所在的单元格也被认为受到了主教的攻击)。

输入

第一行包含一个整数 n (2 ≤ n ≤ 2000)。接下来的 n 行中的每一行都包含 n 个整数 aij (0 ≤ aij ≤ 109) — 棋盘的描述。

输出

在第一行打印 Gargari 将获得的最大美元数。下一行打印四个整数:x1,y1,x2,y2(1≤x1,y1,x2,y2≤n),其中xi是第i个主教应放置的行号,yi是第i个主教应放置的列号。考虑行从上到下从 1 到 n 编号,列从左到右从 1 到 n 编号。

如果有多个最优解,您可以打印其中任意一个。

示例

输入 #1

4
1 1 1 1
2 1 1 0
1 1 1 0
1 0 0 1

输出 #1

12
2 2 3 2