Guess That Car!

题意翻译

**题目描述** awask 在停车场上进行一场“猜车”游戏。 该停车场的南北长度为 $4n$ 米，东西宽度为 $4m$ 米，每 $4$ 米都有一条网格线，把该停车场分割成了 $n \times m$ 个 $16$ 平方米的小块。其中每个小块**的正中心处**都停有一辆车。很容易知道，总共有 $n+1$ 条东西方向的网格线与 $m+1$ 条南北方向的网格线，它们产生了 $(n+1) \times (m+1)$ 个网格点， awask 就需要站在网格点上进行他的猜车游戏。 每一辆车都有一定的价值 $C_{i,j}$ ，若 awask 离某辆车的曼哈顿距离为 $d$ ，那么 awask 猜到该辆车所花费的时间为 $ C_{i,j} \cdot d^2$ 。 现在 awask 只能在这 $(n+1) \times (m+1)$ 个网格点中选择任意一个点开始猜测每一辆车。一旦选择之后，不能更换。希望你能选到一个网格点，使 awask 猜到所有车所花费的时间最少。 提示：请不要使用 %lld 的格式读写64位整数。请使用 cin、cout 或 %I64d。 **输入格式** 第一行两个整数 $n,m (1 \leq n,m \le 1000)$ ，代表该停车场的大小。 接下来 $n$ 行，每行 $m$ 个整数，代表每辆汽车的价值 $C_{i,j}(0 \leq C_{i,j} \le 10^5)$。 **输出格式** 第一行一个数字， awask 猜到所有车所耗费的最小时间。 第二行两个数字，为 awask 所站格点的坐标 $L_{i,j}$。最西北方为 $(0,0)$ ，最东南方为 $(n,m)$。如果有多个符合答案的格点，那么优先选择 $i$ 小的点；如果在 $i$ 相同的一行中同样有多个符合的答案，那么优先选择 $j$ 小的点。 **说明/提示** 第一组数据的汽车价值分别为 | 3 | 4 | 5 | | :----------: | :----------: | :----------: | | 3 | 9 | 1 | 选择 $(1,1)$ 这个位置（在 $3,4,3,9$ 四个数字中间的格点），花费最小，为 $ 3 \cdot8 +3 \cdot8+4 \cdot8+9 \cdot8+5 \cdot40+1 \cdot40=392$ 下图为该停车场的平面坐标系示意图。

题目描述

A widely known among some people Belarusian sport programmer Yura possesses lots of information about cars. That is why he has been invited to participate in a game show called "Guess That Car!". The game show takes place on a giant parking lot, which is $ 4n $ meters long from north to south and $ 4m $ meters wide from west to east. The lot has $ n+1 $ dividing lines drawn from west to east and $ m+1 $ dividing lines drawn from north to south, which divide the parking lot into $ n·m $ $ 4 $ by $ 4 $ meter squares. There is a car parked strictly inside each square. The dividing lines are numbered from $ 0 $ to $ n $ from north to south and from $ 0 $ to $ m $ from west to east. Each square has coordinates $ (i,j) $ so that the square in the north-west corner has coordinates $ (1,1) $ and the square in the south-east corner has coordinates $ (n,m) $ . See the picture in the notes for clarifications. Before the game show the organizers offer Yura to occupy any of the $ (n+1)·(m+1) $ intersection points of the dividing lines. After that he can start guessing the cars. After Yura chooses a point, he will be prohibited to move along the parking lot before the end of the game show. As Yura is a car expert, he will always guess all cars he is offered, it's just a matter of time. Yura knows that to guess each car he needs to spend time equal to the square of the euclidean distance between his point and the center of the square with this car, multiplied by some coefficient characterizing the machine's "rarity" (the rarer the car is, the harder it is to guess it). More formally, guessing a car with "rarity" $ c $ placed in a square whose center is at distance $ d $ from Yura takes $ c·d^{2} $ seconds. The time Yura spends on turning his head can be neglected. It just so happened that Yura knows the "rarity" of each car on the parking lot in advance. Help him choose his point so that the total time of guessing all cars is the smallest possible.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ $ (1<=n,m<=1000) $ — the sizes of the parking lot. Each of the next $ n $ lines contains $ m $ integers: the $ j $ -th number in the $ i $ -th line describes the "rarity" $ c_{ij} $ ( $ 0<=c_{ij}<=100000 $ ) of the car that is located in the square with coordinates $ (i,j) $ .

输出格式

In the first line print the minimum total time Yura needs to guess all offered cars. In the second line print two numbers $ l_{i} $ and $ l_{j} $ ( $ 0<=l_{i}<=n,0<=l_{j}<=m $ ) — the numbers of dividing lines that form a junction that Yura should choose to stand on at the beginning of the game show. If there are multiple optimal starting points, print the point with smaller $ l_{i} $ . If there are still multiple such points, print the point with smaller $ l_{j} $ . Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

2 3
3 4 5
3 9 1

输出样例 #1

392
1 1

输入样例 #2

3 4
1 0 0 0
0 0 3 0
0 0 5 5

输出样例 #2

240
2 3

说明

In the first test case the total time of guessing all cars is equal to 3·8 + 3·8 + 4·8 + 9·8 + 5·40 + 1·40 = 392. The coordinate system of the field: