0282 - 歩くサンタクロース (Walking Santa)

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / Writer root / x 6 / 統計 /

TLE
1sec
MLE
64MB
得点
100

問題

　昨年末，サンタクロースは JOI 村の子供たちにクリスマスプレゼントを渡すのを忘れてしまった．そこで，お詫びの気持ちとして子供たちにチョコレートケーキを届けることにした．届けるべき日は明日に迫っているので，そろそろ移動計画を考えなければならない．
　JOI 村は，南北方向にまっすぐに伸びる W 本の道路と，東西方向にまっすぐに伸びる H 本の道路により，碁盤の目の形に区分けされている. 南北方向の W 本の道路には，西から順に 1, 2, ... , W の番号が付けられており，東西方向の H 本の道路には，南から順に 1, 2, ... , H の番号が付けられている. 西から x 番目の南北方向の道路と，南から y 番目の東西方向の道路が交わる交差点を(x, y) で表す. JOI 村には N 軒の家があり，それらはいずれかの交差点に位置している. サンタクロースは道路に沿ってのみ移動することができる. 隣り合う交差点の間を移動するのにかかる時間を 1 とする.
　JOI 村のすべての家には子供がいるので，サンタクロースは JOI 村のすべての家に 1 個ずつチョコレートケーキを届けてまわらなければならない. 大切なチョコレートケーキを持ってトナカイと空を飛びまわるのはやや危険であるので，サンタクロースとトナカイは JOI 村のいずれかの交差点に降り立ち，サンタクロースがそこから歩いてチョコレートケーキを届けることにした. サンタクロースは同時に 2 個以上のチョコレートケーキを運んで歩くことはしない．つまり，サンタクロースはチョコレートケーキを 1 軒の家に届けるたびに降り立った交差点に戻る．
　サンタクロースは，JOI 村に降り立ってからすべての家にチョコレートケーキを届けるまでの所要時間が最小になるような移動計画を選ぶことにした．ここで，最後の家にチョコレートケーキを届けてから降り立った交差点に戻るまでの時間は所要時間に含めないことに注意せよ．また，移動にかかる時間以外は考えない．

課題

　家の位置の情報が与えられたとき，サンタクロースが降り立つ交差点をうまく選んだ場合の，JOI 村に降り立ってからすべての家にチョコレートケーキを届けるまでの所要時間の最小値と，所要時間を最小にするために降り立つべき交差点の位置を求めるプログラムを作成せよ．

制限

1 ≤ W ≤ 1 000 000 000 = 109    南北方向に伸びる道路の本数
1 ≤ H ≤ 1 000 000 000 = 109    東西方向に伸びる道路の本数
1 ≤ N ≤ 100 000 = 105    家の数
1 ≤ Xi ≤ W    i 番目の家の位置の, 南北方向に伸びる道路の番号
1 ≤ Yi ≤ H    i 番目の家の位置の, 東西方向に伸びる道路の番号

入力

　標準入力から以下のデータを読み込め．

  • 1 行目には各方向の道路の本数を表す整数 W, H が空白を区切りとして書かれている．
  • 2 行目には家の数を表す整数 N が書かれている．
  • 続くN 行には，家の位置の情報が書かれている．i + 2 行目(1 ≤ i ≤ N) には整数 Xi, Yi が空白を区切りとして書かれており，i 番目の家が交差点(Xi, Yi) に位置していることを表す．これら N 個の交差点はすべて異なる．

出力

　標準出力に以下のデータを出力せよ．

  • 1 行目には所要時間の最小値を表す 1 つの整数が書かれていなければならない．
  • 2 行目には所要時間を最小にするために降り立つべき交差点が(x, y) であるとき，2 つの整数 x, y がこの順に空白を区切りとして書かれていなければならない．適切な交差点が複数ある場合は，そのうち最も西にある(つまり，x の値が小さい) 交差点を, それでも 1 つに定まらない場合は, さらにそのうちで最も南にある(つまり，y の値が小さい) 交差点を選べ.

注意

　この問題では，扱う整数の範囲が32 ビットに収まらない可能性があることに注意せよ．

採点基準

　採点用データのうち，配点の 40 %分については，N ≤ 1 000 を満たす．
　採点用データのうち，配点の 10 %分については，W ≤ 50, H ≤ 50, N ≤ 1 000 を満たす．

入出力例

入力例 1

5 4
3
1 1
3 4
5 3

出力例 1

10
3 3

　たとえば，次のような移動計画により所要時間を最小にできる．

  • 交差点(3, 3) に降り立つ．
  • 交差点(3, 4) に位置している家にチョコレートケーキを届ける．ここまでの経過時間は 1 である．
  • 交差点(3, 3) に戻る．ここまでの経過時間は 2 である．
  • 交差点(5, 3) に位置している家にチョコレートケーキを届ける．ここまでの経過時間は 4 である．
  • 交差点(3, 3) に戻る．ここまでの経過時間は 6 である．
  • 交差点(1, 1) に位置している家にチョコレートケーキを届ける．ここまでの経過時間は 10 である．

入力例 2

4 6
8
1 3
3 2
4 4
2 5
2 3
3 3
3 4
2 4

出力例 2

21
2 3

　家がある交差点に降り立ってもよいことに注意せよ．