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