Rating changes for last rounds are temporarily rolled back. They will be returned soon.
×

Codeforces Round 264 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

hashing

implementation

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Gargari and Bishops

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputGargari is jealous that his friend Caisa won the game from the previous problem. He wants to prove that he is a genius.

He has a *n* × *n* chessboard. Each cell of the chessboard has a number written on it. Gargari wants to place two bishops on the chessboard in such a way that there is no cell that is attacked by both of them. Consider a cell with number *x* written on it, if this cell is attacked by one of the bishops Gargari will get *x* dollars for it. Tell Gargari, how to place bishops on the chessboard to get maximum amount of money.

We assume a cell is attacked by a bishop, if the cell is located on the same diagonal with the bishop (the cell, where the bishop is, also considered attacked by it).

Input

The first line contains a single integer *n* (2 ≤ *n* ≤ 2000). Each of the next *n* lines contains *n* integers *a*_{ij} (0 ≤ *a*_{ij} ≤ 10^{9}) — description of the chessboard.

Output

On the first line print the maximal number of dollars Gargari will get. On the next line print four integers: *x*_{1}, *y*_{1}, *x*_{2}, *y*_{2} (1 ≤ *x*_{1}, *y*_{1}, *x*_{2}, *y*_{2} ≤ *n*), where *x*_{i} is the number of the row where the *i*-th bishop should be placed, *y*_{i} is the number of the column where the *i*-th bishop should be placed. Consider rows are numbered from 1 to *n* from top to bottom, and columns are numbered from 1 to *n* from left to right.

If there are several optimal solutions, you can print any of them.

Examples

Input

4

1 1 1 1

2 1 1 0

1 1 1 0

1 0 0 1

Output

12

2 2 3 2

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/24/2024 11:53:12 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|