Deskripsi Soal

Pada akhir tahun lalu, Sinterklas lupa memberikan hadiah Natal kepada anak-anak di Desa JOI. Oleh karena itu, sebagai permintaan maaf, ia memutuskan untuk mengantarkan kue cokelat kepada anak-anak tersebut. Karena hari pengantarannya adalah besok, ia harus segera memikirkan rencana perjalanan.

Desa JOI terbagi menjadi bentuk petak-petak seperti papan catur oleh $W$ jalan lurus berarah utara-selatan dan $H$ jalan lurus berarah timur-barat. $W$ jalan berarah utara-selatan diberi nomor $1, 2, \dots, W$ secara berurutan dari barat, dan $H$ jalan berarah timur-barat diberi nomor $1, 2, \dots, H$ secara berurutan dari selatan. Persimpangan tempat jalan utara-selatan ke-$x$ dari barat dan jalan timur-barat ke-$y$ dari selatan bertemu dinyatakan dengan $(x, y)$. Terdapat $N$ rumah di Desa JOI, dan masing-masing terletak di salah satu persimpangan. Sinterklas hanya dapat bergerak di sepanjang jalan. Waktu yang diperlukan untuk bergerak di antara dua persimpangan yang bersebelahan adalah $1$.

Karena di semua rumah di Desa JOI terdapat anak-anak, Sinterklas harus mengunjungi semua rumah di Desa JOI untuk mengantarkan masing-masing $1$ kue cokelat. Karena terbang berkeliling di angkasa bersama rusa kutub sambil membawa kue cokelat yang berharga cukup berbahaya, Sinterklas dan rusa kutubnya memutuskan untuk mendarat di salah satu persimpangan di Desa JOI, lalu Sinterklas akan berjalan kaki dari sana untuk mengantarkan kue cokelat. Sinterklas tidak akan berjalan sambil membawa $2$ atau lebih kue cokelat secara bersamaan. Artinya, setiap kali Sinterklas selesai mengantarkan kue cokelat ke $1$ rumah, ia kembali ke persimpangan tempat ia mendarat.

Sinterklas memutuskan untuk memilih rencana perjalanan yang meminimalkan total waktu yang diperlukan sejak mendarat di Desa JOI hingga selesai mengantarkan kue cokelat ke semua rumah. Perhatikan bahwa waktu yang diperlukan untuk kembali ke persimpangan tempat mendarat setelah mengantarkan kue cokelat ke rumah terakhir tidak dimasukkan ke dalam total waktu yang diperlukan. Selain itu, hal-hal selain waktu yang diperlukan untuk bergerak tidak diperhitungkan.

Diberikan informasi lokasi rumah-rumah, buatlah program untuk mencari nilai minimum dari waktu yang diperlukan sejak mendarat di Desa JOI hingga selesai mengantarkan kue cokelat ke semua rumah apabila Sinterklas memilih persimpangan tempat mendarat dengan tepat, serta mencari posisi persimpangan tempat ia harus mendarat untuk meminimalkan waktu yang diperlukan.

Format Masukan

Bacalah masukan berikut dari Masukan Standar:

• Baris ke-$1$ berisi bilangan bulat $W, H$ yang dipisahkan oleh spasi, menyatakan banyaknya jalan di masing-masing arah.
• Baris ke-$2$ berisi sebuah bilangan bulat $N$, menyatakan banyaknya rumah.
• $N$ baris berikutnya berisi informasi posisi rumah. Baris ke-$(i + 2)$ ($1 \le i \le N$) berisi bilangan bulat $X_i, Y_i$ yang dipisahkan oleh spasi, menyatakan bahwa rumah ke-$i$ terletak di persimpangan $(X_i, Y_i)$. Ke-$N$ persimpangan ini semuanya berbeda.

Format Keluaran

Keluarkan data berikut ke Keluaran Standar:

• Baris ke-$1$ harus berisi $1$ bilangan bulat yang menyatakan nilai minimum waktu yang diperlukan.
• Baris ke-$2$: apabila persimpangan tempat mendarat untuk meminimalkan waktu yang diperlukan adalah $(x, y)$, maka harus berisi $2$ bilangan bulat $x, y$ dengan urutan ini yang dipisahkan oleh spasi. Jika terdapat beberapa persimpangan yang sesuai, pilihlah yang paling barat (yaitu yang nilai $x$-nya paling kecil) di antaranya; jika masih belum dapat ditentukan menjadi $1$ pilihan, pilihlah yang paling selatan (yaitu yang nilai $y$-nya paling kecil) di antaranya.

Contoh

Contoh 1

Masukan

5 4
3
1 1
3 4
5 3

Keluaran

10
3 3

Penjelasan

Sebagai contoh, waktu yang diperlukan dapat diminimalkan dengan rencana perjalanan berikut:

• Mendarat di persimpangan $(3, 3)$.
• Mengantarkan kue cokelat ke rumah yang terletak di persimpangan $(3, 4)$. Waktu yang telah berlalu hingga titik ini adalah $1$.
• Kembali ke persimpangan $(3, 3)$. Waktu yang telah berlalu hingga titik ini adalah $2$.
• Mengantarkan kue cokelat ke rumah yang terletak di persimpangan $(5, 3)$. Waktu yang telah berlalu hingga titik ini adalah $4$.
• Kembali ke persimpangan $(3, 3)$. Waktu yang telah berlalu hingga titik ini adalah $6$.
• Mengantarkan kue cokelat ke rumah yang terletak di persimpangan $(1, 1)$. Waktu yang telah berlalu hingga titik ini adalah $10$.

Contoh 2

Masukan

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

Keluaran

21
2 3

Penjelasan

Perhatikan bahwa Sinterklas boleh saja mendarat di persimpangan yang terdapat rumah.

Batasan

• $1 \le W \le 1000000000 = 10^9$: banyaknya jalan yang membentang ke arah utara-selatan.
• $1 \le H \le 1000000000 = 10^9$: banyaknya jalan yang membentang ke arah timur-barat.
• $1 \le N \le 100000 = 10^5$: banyaknya rumah.
• $1 \le X_i \le W$: nomor jalan arah utara-selatan dari posisi rumah ke-$i$.
• $1 \le Y_i \le H$: nomor jalan arah timur-barat dari posisi rumah ke-$i$.

Perhatikan bahwa pada soal ini, rentang bilangan bulat yang ditangani mungkin tidak muat dalam $32$ bit.

Kriteria Penilaian

• Untuk kasus uji senilai $40\%$ dari total nilai, berlaku $N \le 1000$.
• Untuk kasus uji senilai $10\%$ dari total nilai, berlaku $W \le 50, H \le 50, N \le 1000$.